भारी गोली: एक तौल से भारी शीशी ढूँढ़ो (जावा)

टीएल;डीआर

समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।

दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली की समस्या ६.१: बीस गोली की शीशियाँ, एक में १.० ग्रा के बजाय १.१ ग्रा की गोलियाँ। १, २, ..., २० गोलियाँ लेकर एक तौल से अतिरिक्त वजन पढ़कर भारी शीशी पहचानो।

जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।

तुम्हारे पास गोलियों की २० शीशियाँ हैं। उन्नीस शीशियों में सामान्य गोलियाँ हैं, हर गोली १.० ग्राम। एक शीशी में भारी गोलियाँ हैं, हर गोली १.१ ग्राम। शीशियाँ एक जैसी दिखती हैं। पास में ऐसा तराजू है जो सही वजन बताता है, और तुम उसे केवल एक बार इस्तेमाल कर सकते हो। भारी शीशी कौन सी है?

यह पहले तर्क की पहेली है, कोड बाद में। क्लासिक चाल यह है कि हर शीशी से अलग संख्या में गोलियाँ तराजू पर रखो, ताकि अतिरिक्त द्रव्यमान शीशी का सूचकांक कूटबद्ध करे। यह पोस्ट शुरुआती लोगों के लिए मूल शिक्षण है, वैकल्पिक जावा से तौल का अनुकरण। इंटरव्यू वाली गणित पहेलियों का परिवार, किताब की नकल नहीं। सीटीसीआई जावा सीरीज़ का हिस्सा। अध्याय ६, गणित और तर्क, यहीं से शुरू।

१. रोज़मर्रा की उपमा

बीस बंद कॉफी के जार सोचो। उन्नीस में साधारण दाने। एक में थोड़े सघन दाने। रसोई के तराजू पर सिर्फ एक बार जाना है।

अगर जार १ से एक दाना, जार २ से एक, और ऐसे ही तौलो, तो ज़्यादा रीडिंग सिर्फ कहती है "कुछ गड़बड़ है"। कौन सा जार, यह नहीं कहती।

हर जार को ढेर में अलग पहचान दो। जार १ से १ दाना, जार २ से २, ..., जार २० से २०। अगर हर दाना सामान्य होता तो कुल निश्चित रहता। कोई भी अतिरिक्त वजन सिर्फ सघन जार से आता है, और उस अतिरिक्त की मात्रा उसी जार से ली गई दानों की संख्या के समानुपाती है। अतिरिक्त ही जार का नंबर है।

२. समस्या सादे शब्दों में

सेटअप:

२० शीशियाँ, १ से २० तक लेबल (या ० से १९; एक चुनो और उसी पर टिके रहो)।
१९ शीशियाँ: हर गोली १.० ग्रा।
१ शीशी: हर गोली १.१ ग्रा।
पता नहीं कौन सी भारी है।
संख्यात्मक तराजू (सिर्फ बाएँ/दाएँ/बराबर बताने वाला नहीं)।
केवल एक तौल।

लक्ष्य: उस एक माप के बाद भारी शीशी का नाम बताओ।

इंटरव्यू में कहने वाले अनुमान:

हर शीशी में काफी गोलियाँ (शीशी २० में कम से कम २०)।
एक शीशी की गोलियाँ एकसमान।
ठीक एक भारी शीशी (शून्य नहीं, दो नहीं)।
तराजू की सटीकता ०.१ ग्रा के कदम देख सके (या बेहतर)।

अगर सिम्युलेटर लिखो तो सिग्नेचर का आकार:

// bottles[i] is true if bottle i (1-based in comments, 0-based in arrays) is heavy
// returns the 1-based bottle index inferred from one weighing
int findHeavyBottle(boolean[] isHeavy);

या पहेली के लिए ज़्यादा ईमानदार:

// given the true heavy bottle (1..20), simulate the weighing strategy and recover it
int identifyHeavy(int trueHeavyBottle);

छोटा संख्यात्मक पूर्वावलोकन:

कुल 1 + 2 + ... + 20 = 210 गोलियाँ। अगर सब १.० ग्रा होतीं तो तराजू २१०.० ग्रा दिखाता।

अगर शीशी k भारी है, तो वे k गोलियाँ हर एक ०.१ ग्रा अतिरिक्त देती हैं, इसलिए:

measured = 210.0 + 0.1 * k
k = (measured - 210.0) / 0.1

उदाहरण: माप २१०.७ ग्रा → अतिरिक्त ०.७ ग्रा → शीशी ७।

३. पहले सोचो

हर शीशी से एक गोली क्यों फेल

हर शीशी से एक गोली: २० गोलियाँ। सब सामान्य हों तो २०.० ग्रा। अगर भारी शीशी उनमें है तो २०.१ ग्रा। पता चलता है भारी शीशी मौजूद है, पर हर भारी शीशी वही +०.१ ग्रा जोड़ती। कौन सी, इस पर शून्य जानकारी।

बाइनरी खोज जैसी चालें (आधी शीशियाँ, फिर आधी) को कई तौल चाहिए। समस्या तुम्हें एक पर बाँधती है।

अतिरिक्त वजन में शीशी का सूचकांक कूटबद्ध करो

हर शीशी को कुल वजन पर अलग हस्ताक्षर छोड़ना चाहिए। अलग गिनती यही करती है:

शीशी	ली गई गोलियाँ	भारी होने पर अतिरिक्त
१	१	०.१ ग्रा
२	२	०.२ ग्रा
३	३	०.३ ग्रा
...	...	...
२०	२०	२.० ग्रा

सब-सामान्य आधाररेखा:

sum = 1 + 2 + ... + 20 = n(n+1)/2 = 20*21/2 = 210
baseline weight = 210.0 g

सिर्फ भारी शीशी की गोलियाँ ०.१ ग्रा ज़्यादा। अगर शीशी k भारी:

weight = (210 - k) * 1.0 + k * 1.1
       = 210 + 0.1 * k

इसलिए:

k = round((weight - 210.0) / 0.1)

कोड में राउंडिंग इस्तेमाल करो क्योंकि फ्लोटिंग पॉइंट गंदा है। कागज़ पर सटीक अंकगणित काफी है।

यह "गणित और तर्क" क्यों है, छँटाई नहीं

कोई ऐरे छाँटना नहीं। अंतर्दृष्टि है सतत माप पर सूचना सिद्धांत: एक वास्तविक संख्या में इतनी विभेदन क्षमता है कि अगर नमूना सोच-समझकर बनाओ तो वह पूर्णांक पहचान ढो सकती है। इंटरव्यूअर चाहते हैं कि तुम कूटगठन गढ़ो, "२१०" रट लो नहीं।

जो लोग लाते हैं वे वेरिएंट

कुछ हल्की, कुछ भारी, या दिशा अज्ञात: अलग क्लासिक पहेलियाँ (अक्सर तराजू के दो पलड़े और ज़्यादा तौल)। जब तक न पूछें मिलाओ मत।
शीशियाँ ०..१९: शीशी ० से ० गोलियाँ? बेकार। १..२० पर फिर से नंबर दो, या शीशी i से i+1 लो।
सिर्फ तुलना वाला तराजू (बायाँ बनाम दायाँ): इस समस्या का तराजू आमतौर पर संख्यात्मक है। साफ करो। सिर्फ बाएँ/दाएँ पर अलग रणनीति और अक्सर ज़्यादा उपयोग।

४. जावा समाधान (अनुकरण)

पहेली तर्क से सुलझती है। कोड साफ तरीका है दिखाने का कि योजना फ्लोटिंग-पॉइंट के खतरों के बिना लागू हो सकती है।

मूल गणित सहायक

/** Sum 1+2+...+n. For n=20 this is 210. */
static int triangular(int n) {
    return n * (n + 1) / 2;
}

/**
 * Infer heavy bottle (1..n) from measured total grams.
 * baseline is triangular(n) assuming 1.0 g pills.
 */
static int bottleFromWeight(double measuredGrams, int n) {
    double baseline = triangular(n); // 210.0 for n=20
    double excess = measuredGrams - baseline;
    // each heavy pill adds 0.1 g; k pills add 0.1*k
    int k = (int) Math.round(excess / 0.1);
    if (k < 1 || k > n) {
        throw new IllegalArgumentException(
            "weight does not match any bottle: " + measuredGrams);
    }
    return k;
}

एक सच्ची भारी शीशी का अनुकरण

/**
 * Simulate the classic strategy for bottles 1..n.
 * trueHeavy is 1-based. Returns the bottle index recovered from one weighing.
 */
static int identifyHeavy(int trueHeavy, int n) {
    if (trueHeavy < 1 || trueHeavy > n) {
        throw new IllegalArgumentException("trueHeavy out of range");
    }

    // one weighing: take i pills from bottle i
    double weight = 0.0;
    for (int bottle = 1; bottle <= n; bottle++) {
        int count = bottle;
        double pillMass = (bottle == trueHeavy) ? 1.1 : 1.0;
        weight += count * pillMass;
    }

    return bottleFromWeight(weight, n);
}

सभी २० मामलों की स्व-जाँच

static void verifyAll() {
    int n = 20;
    for (int heavy = 1; heavy <= n; heavy++) {
        int found = identifyHeavy(heavy, n);
        if (found != heavy) {
            throw new AssertionError("failed for bottle " + heavy);
        }
    }
    System.out.println("ok: all " + n + " bottles identified");
}

मॉडल में फ्लोट से बचो (वैकल्पिक, साफ)

द्रव्यमान को ग्राम के दसवें में लो: सामान्य गोली = १० इकाइयाँ, भारी = ११। सब पूर्णांक।

static int identifyHeavyInt(int trueHeavy, int n) {
    // units of 0.1 g: normal=10, heavy=11
    int weightUnits = 0;
    for (int bottle = 1; bottle <= n; bottle++) {
        int count = bottle;
        int pill = (bottle == trueHeavy) ? 11 : 10;
        weightUnits += count * pill;
    }
    int baselineUnits = triangular(n) * 10; // 2100
    int extraUnits = weightUnits - baselineUnits; // equals trueHeavy
    return extraUnits; // 1..n
}

इंटरव्यू के अनुकूल वाक्य: "मैं ग्राम के दसवें में सोचूँगा ताकि व्हाइटबोर्ड पर फ्लोट न बाँटना पड़े।"

काम किए हुए अंक

शीशी १२ भारी, n = 20:

baseline = 210.0 g
extra    = 12 * 0.1 = 1.2 g
measured = 211.2 g
k        = 1.2 / 0.1 = 12

पूर्णांक इकाइयाँ:

baseline = 2100
measured = 2100 + 12 = 2112
extra    = 12

५. जटिलता तालिका

तरीका	समय	अतिरिक्त स्थान	नोट
शीशी क्रमांक से उतनी गोलियाँ, एक तौल	नमूना बनाने में ओ(एन)	ओ(१)	एन शीशियाँ; हाथ से भी वही
हर शीशी से एक गोली (अकेली बेकार)	ओ(एन)	ओ(१)	सिर्फ बताती है "कोई भारी शीशी है"
कई तौल वाली बाइनरी खोज	ओ(लॉग एन) तौल	ओ(१)	एक-तौल नियम तोड़ती है
पूरी शीशियाँ एक-दूसरे से तोलो	बदलता है	ओ(१)	पलड़े वाली रणनीति; अलग पहेली

दिलचस्प लागत है तोलों की संख्या: १, एसिम्प्टोटिक रनटाइम नहीं। कोड में नमूना बनाना ओ(एन) अंकगणित है।

६. किनारे के मामले और आम गलतियाँ

इंटरव्यूअर ये छेदते हैं:

शीशी १ भारी: अतिरिक्त ०.१ ग्रा। अगर सिर्फ "बड़े" फर्क सोचो तो चूक जाती है।
शीशी २० भारी: अतिरिक्त २.० ग्रा। माप २१२.० ग्रा। फिर भी अद्वितीय।
ऑफ-बाय-वन लेबल: शीशियाँ ०..१९ बनाम १..२०। लेबल साफ बोलो। extra/0.1 को अपने सूचकांक स्कीम पर मैप करो।
फ्लोटिंग पॉइंट: 211.2 - 210.0 कभी 1.199999... बन जाता है। Math.round या पूर्णांक दसवें पसंद करो।
शीशी में कम गोलियाँ: रणनीति को शीशी २० से २० गोलियाँ चाहिए। पुष्टि करो कि कथन अनुमति देता है (क्लासिक में हाँ)।
सिर्फ दो पलड़े तुलना करने वाला तराजू: अलग समस्या। पूछो।
सब सामान्य या कई भारी होने की संभावना: क्लासिक ६.१ मानता है ठीक एक भारी शीशी।
हर शीशी से एक जैसी गिनती: सारे हस्ताक्षर एक अतिरिक्त मान में मिल जाते हैं।

आम गलतियाँ:

१. पूरी शीशियाँ एक बार तौलना बिना ऐसी योजना के जो सूचकांक अलग करे। २. बाइनरी समूह मानना जैसे पास लॉग₂(२०) तौल हों। ३. आधाररेखा भूलना और २१० घटाए बिना निरपेक्ष वजन पढ़ना। ४. अतिरिक्त को १.१ या ०.०१ से भाग देना (गलत इकाई)। भारी गोली प्रति अतिरिक्त ०.१ ग्रा है। ५. जटिलता ओ(१) तौल कहना और फिर कोड में तोलों का लूप लिखना, विरोधाभास न देखना।

न्यूनतम स्मोक विचार:

verifyAll();
System.out.println(identifyHeavy(7, 20));  // 7
System.out.println(identifyHeavy(20, 20)); // 20
System.out.println(identifyHeavyInt(12, 20)); // 12

७. दोस्त को समझाओ सार

बीस शीशियाँ। एक में भारी गोलियाँ। संख्यात्मक तराजू पर एक तौल।

१. हर शीशी से एक जैसी संख्या मत लो। वह सिर्फ कहती है "कोई भारी है"। २. शीशी १ से १, शीशी २ से २, ..., शीशी २० से २० लो। ३. सब सामान्य हो तो कुल द्रव्यमान २१० ग्रा। ४. भारी शीशी k जोड़ती है ०.१ × k ग्राम। ५. k = (मापा - २१०) / ०.१ निकालो। यही उत्तर। ६. कोड में ग्राम के पूर्णांक दसवें पसंद करो, ताकि फ्लोट शर्मिंदा न करे।

अगर बिना लूप लिखे समझा सको कि अतिरिक्त ही शीशी का नंबर क्यों है, तो समस्या ६.१ तुम्हारी है। अध्याय ६ इसी अंदाज़ से भरा है: कोई माप या निश्चर गढ़ो, फिर कोड छोटा रह जाता है।