पानी के जग: तीन और पाँच से ठीक चार लीटर मापो (जावा)

टीएल;डीआर

• समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।
• दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली की समस्या ६.५: क्षमता ३ और ५ लीटर के दो जग, ठीक ४ लीटर मापो। हाथ से डालने के चरण, बेज़ू पहचान, और वैकल्पिक जावा बीएफएस राज्य खोज।
• जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।

तुम्हारे पास ३ लीटर का एक जग है और ५ लीटर का दूसरा। और कोई निशान नहीं। भरने के लिए असीमित झील (या नल), और किसी भी जग को पूरी तरह खाली कर सकते हो। क्या किसी एक में ठीक ४ लीटर ला सकते हो?

यह क्लासिक पानी-जग पहेली है। रसोई में संख्या सिद्धांत भी है: जो मात्राएँ माप सकते हो वे gcd(3, 5) के गुणज हैं, जो १ है, इसलिए ४ संभव है। इंटरव्यू में चरण, कारण, और कभी-कभी खोज वाला प्रोग्राम चाहिए जो चरण निकाले।

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

---

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

आधे लीटर की रेखाओं के बिना दो मापक गिलास सोचो। एक में तीन गिलास पानी समाए, दूसरे में पाँच। तुम कर सकते हो:

• नल से एक गिलास पूरा भरना।
• एक गिलास पूरा खाली करना।
• एक से दूसरे में तब तक डालना जब तक स्रोत खाली हो या गंतव्य भर जाए।

आधे भराव "आँख से" कभी नहीं। हर मात्रा पूरे भरने, पूरे खाली करने, और क्षमता पर रुकने वाले डालने से बनती है। पहेली: क्या इन चालों की छोटी कड़ी के बाद एक जग में ४ लीटर दिखता है।

---

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

दिया:

• जग ए क्षमता: ३ लीटर।
• जग बी क्षमता: ५ लीटर।
• असीमित पानी स्रोत और खाली करने की जगह (किसी को भी पूरा खाली कर सकते हो)।

अनुमत संचालन:

१. स्रोत से ए पूरा भरना। २. स्रोत से बी पूरा भरना। ३. ए पूरा खाली करना। ४. बी पूरा खाली करना। ५. ए को बी में डालना जब तक ए खाली हो या बी भर जाए। ६. बी को ए में डालना जब तक बी खाली हो या ए भर जाए।

लक्ष्य: कोई भी अवस्था जहाँ ए या बी (या दोनों) में ठीक ४ लीटर हो। आम कथन में ४, ५ लीटर वाले जग में आता है।

कोड या चरण लिखने से पहले साफ़ करो:

• क्या ४ एक ही जग में होना चाहिए? (इस क्लासिक संस्करण में हाँ।)
• तीसरा बर्तन? (नहीं।)
• शुरू में खाली? (हाँ।)
• सिर्फ पूर्णांक लीटर? (हाँ: पूर्णांक मात्राएँ।)
• बाद में सामान्य मामला: क्षमताएँ m, n, लक्ष्य d। वही विचार।

---

३. पहले सोचो

सच में क्या माप सकते हो

हर चाल या तो:

• पूरी क्षमता जोड़ती है (भरने पर स्रोत से +3 या +5),
• पूरी क्षमता घटाती है (खाली करने पर),
• या जगों के बीच पानी घुमाती है, बिना मौजूदा कुल पानी बदले।

अगर सिर्फ एक जग में दिखने वाली मात्राएँ देखो, वे ३ और ५ के पूर्णांक रैखिक संयोजन हैं:

a*3 + b*5   कुछ पूर्णांक a, b के लिए (धनात्मक या ऋणात्मक)

ऋणात्मक का मतलब क्लासिक हिसाब में "उतनी बार खाली करना"। बेज़ू पहचान: ऐसे सभी संयोजन ठीक gcd(3, 5) = 1 के गुणज हैं। इसलिए एक जग में १, २, ३, ४ या ५ लीटर माप सकते हो (क्षमता के भीतर)। ६ और ९ के जग से ४ नहीं माप सकते, क्योंकि gcd(6, 9) = 3 और ३, ४ को नहीं बाँटता।

सामान्य पहेली का नियम: लक्ष्य d हल करने योग्य है अगर और केवल अगर d, gcd(m, n) का गुणज है और 0 < d <= max(m, n) ("एक जग में ठीक d" के लिए)।

जादू नहीं, अवस्थाएँ

अवस्था एक जोड़ा (a, b) है: ३-जग में लीटर और ५-जग में लीटर।

• शुरू: (0, 0)।
• लक्ष्य: कोई अवस्था जहाँ a == 4 या b == 4। यहाँ सिर्फ बी में ४ समा सकता है, इसलिए b == 4।

हर अवस्था से ज़्यादा से ज़्यादा छह चालें। ग्राफ़ छोटा है: ए के ४ मान (०..३) गुणा बी के ६ (०..५) = २४ अवस्थाएँ। चौड़ाई-पहले खोज सबसे छोटी कड़ी निकालती है अगर कोड चाहिए। बोर्ड पर एक छोटा हाथ-कदम का रास्ता काफ़ी है।

एक साफ़ हाथ-कदम रास्ता (६ डाल)

(३-जग, ५-जग) ट्रैक करो:

(0, 0)  शुरू
(0, 5)  ५ भरें
(3, 2)  ५ को ३ में डालें जब तक ३ भर जाए; ५ में २ बचे
(0, 2)  ३ खाली करें
(2, 0)  बचे २ को ३ में डालें
(2, 5)  फिर ५ भरें
(3, 4)  ५ को ३ में डालें जब तक ३ भर जाए (१ और चाहिए); ५ में ४ बचे

हो गया। ५ लीटर वाले जग में ठीक ४ लीटर।

दूसरा रास्ता (३ से शुरू)

(0, 0)
(3, 0)  ३ भरें
(0, 3)  ५ में डालें
(3, 3)  ३ भरें
(1, 5)  ५ भरने तक डालें; ३ में १ बचा
(1, 0)  ५ खाली करें
(0, 1)  वह १, ५ में डालें
(3, 1)  ३ भरें
(0, 4)  ५ में डालें; ५ में १+३ = ४

लंबा, वही विचार: ५ के सापेक्ष ३ के शेष बनाते हो (या उलटा)।

---

४. जावा समाधान

(क) हाथ की विधि लिखो (अक्सर इंटरव्यू में पहले यही चाहिए)

// Manual sequence for (3, 5) -> 4 in the five-liter jug.
// States written as (small, large).
//
// (0,0) fill large  -> (0,5)
// pour large->small -> (3,2)
// empty small       -> (0,2)
// pour large->small -> (2,0)
// fill large        -> (2,5)
// pour large->small -> (3,4)  // large has 4

ज़ोर से बोलो, फिर बेज़ू जाँच लिखो ताकि लगे कि अटकल नहीं है।

(ख) हल-योग्यता सहायक (सामान्य m, n, d)

static int gcd(int x, int y) {
    x = Math.abs(x);
    y = Math.abs(y);
    while (y != 0) {
        int t = x % y;
        x = y;
        y = t;
    }
    return x;
}

/** True if you can obtain exactly d liters in one jug of capacities m and n. */
static boolean canMeasure(int m, int n, int d) {
    if (d == 0) {
        return true; // both empty
    }
    if (m + n < d) {
        return false;
    }
    // Exactly d in one jug: d must fit in at least one jug
    if (d > m && d > n) {
        return false;
    }
    return d % gcd(m, n) == 0;
}

m = 3, n = 5, d = 4 के लिए: gcd १ है, ४ पाँच में समाता है, इसलिए सही।

(ग) वैकल्पिक: अवस्थाओं पर बीएफएस (सबसे छोटी चरण सूची)

जब क्षमताएँ बड़ी हों या प्रोग्राम माँगें तब काम आता है। अवस्था स्थान (m+1)*(n+1) है।

import java.util.*;

public class WaterJugs {
    record State(int a, int b) {}

    static List<String> measure(int m, int n, int d) {
        if (!canMeasure(m, n, d) && d != 0) {
            return List.of(); // impossible
        }
        if (d == 0) {
            return List.of("start (0,0)");
        }

        Queue<State> q = new ArrayDeque<>();
        Map<State, String> how = new HashMap<>(); // state -> last move label
        Map<State, State> prev = new HashMap<>();

        State start = new State(0, 0);
        q.add(start);
        how.put(start, "start");
        prev.put(start, null);

        while (!q.isEmpty()) {
            State cur = q.poll();
            if (cur.a == d || cur.b == d || cur.a + cur.b == d) {
                // classic "in one jug": prefer a==d or b==d
                if (cur.a == d || cur.b == d) {
                    return reconstruct(cur, prev, how);
                }
            }

            for (Object[] step : neighbors(cur, m, n)) {
                State nxt = (State) step[0];
                String label = (String) step[1];
                if (how.containsKey(nxt)) {
                    continue;
                }
                how.put(nxt, label);
                prev.put(nxt, cur);
                q.add(nxt);
            }
        }
        return List.of(); // unreachable (should not happen if canMeasure)
    }

    static List<Object[]> neighbors(State s, int m, int n) {
        int a = s.a, b = s.b;
        List<Object[]> out = new ArrayList<>();
        out.add(new Object[]{new State(m, b), "fill A"});
        out.add(new Object[]{new State(a, n), "fill B"});
        out.add(new Object[]{new State(0, b), "empty A"});
        out.add(new Object[]{new State(a, 0), "empty B"});

        // pour A -> B
        int pourAB = Math.min(a, n - b);
        out.add(new Object[]{new State(a - pourAB, b + pourAB), "pour A->B"});

        // pour B -> A
        int pourBA = Math.min(b, m - a);
        out.add(new Object[]{new State(a + pourBA, b - pourBA), "pour B->A"});
        return out;
    }

    static List<String> reconstruct(State end, Map<State, State> prev, Map<State, String> how) {
        LinkedList<String> path = new LinkedList<>();
        State cur = end;
        while (cur != null) {
            path.addFirst(how.get(cur) + " -> (" + cur.a + "," + cur.b + ")");
            cur = prev.get(cur);
        }
        return path;
    }

    static boolean canMeasure(int m, int n, int d) {
        if (d == 0) return true;
        if (d > m && d > n) return false;
        if (m + n < d) return false;
        return d % gcd(m, n) == 0;
    }

    static int gcd(int x, int y) {
        x = Math.abs(x);
        y = Math.abs(y);
        while (y != 0) {
            int t = x % y;
            x = y;
            y = t;
        }
        return x;
    }

    public static void main(String[] args) {
        System.out.println(canMeasure(3, 5, 4)); // true
        for (String step : measure(3, 5, 4)) {
            System.out.println(step);
        }
    }
}

बीएफएस एक सबसे छोटा रास्ता लौटाता है। ऊपर वाला छह-चरण हाथ-रास्ता ४ लीटर के लिए न्यूनतम लंबाई का है; लंबा "३ से शुरू" रास्ता सही है पर न्यूनतम नहीं।

डाल की गणित

जब ए को बी में डालते हो:

spaceInB = n - b
moved = min(a, spaceInB)
newA = a - moved
newB = b + moved

उलटी दिशा में वही विचार। पूरी सिमुलेशन यही है। कोई फ्लोट नहीं।

---

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

तरीका	समय	अतिरिक्त स्थान	नोट
हाथ की ६-चरण विधि	ओ(१)	ओ(१)	स्थिर ३ और ५ के लिए काफ़ी
बेज़ू / जीसीडी जाँच	ओ(लॉग न्यूनतम(m,n))	ओ(१)	सिर्फ हल-योग्यता, चरण नहीं
अवस्थाओं पर बीएफएस	ओ(m * n)	ओ(m * n)	संचालन की सबसे छोटी कड़ी
डीएफएस / पुनरावृत्ति	वही क्रम	ढेर कभी बदतर	सबसे छोटे रास्ते के लिए बीएफएस बेहतर

इंटरव्यू आकार जैसे ३ और ५ में स्थिरांक हावी रहते हैं। जीसीडी जाँच साफ़ सैद्धांतिक औज़ार है।

---

६. किनारे के मामले

• लक्ष्य ० → पहले से हल: दोनों खाली।
• लक्ष्य किसी क्षमता के बराबर → एक भरना। उदाहरण: ३ क्षमता वाले जग से लक्ष्य ३।
• लक्ष्य दोनों जगों से बड़ा → एक जग में d चाहिए तो असंभव।
• gcd लक्ष्य d को नहीं बाँटता → असंभव। उदाहरण: ६ और ९ से ४।
• एक क्षमता ० → सिर्फ दूसरी के गुणज (आमतौर पर ० और वह क्षमता)।
• समान क्षमताएँ → एक जग में सिर्फ ० या वही क्षमता।
• ४ बड़े जग में चाहिए → सिर्फ b == 4 जाँचो, या कोई भी जग मानो।
• आधे लीटर मत गढ़ो → मात्राएँ पूर्णांक रहें।
• लीटकोड ३६५ शैली → "माप सकते हो" के लिए जीसीडी काफ़ी; "चरण छापो" के लिए बीएफएस या स्पष्ट निर्माण।

न्यूनतम जाँच:

assert canMeasure(3, 5, 4);
assert canMeasure(3, 5, 1);
assert !canMeasure(2, 6, 5);
assert canMeasure(3, 5, 0);

---

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

पानी के जग पूछते हैं: सिर्फ पूरे भरने, पूरे खाली करने, और ३ व ५ के बीच डालने से क्या ठीक ४ लीटर मिल सकता है?

१. चालें सिर्फ ३ और ५ के पूर्णांक संयोजन बनाती हैं। २. वे संयोजन gcd(3, 5) = 1 के गुणज हैं, इसलिए ४ संभव है और ५ लीटर वाले जग में समाता है। ३. छोटी विधि: ५ भरें, ३ में डालें, ३ खाली करें, बचे २ को ३ में डालें, ५ भरें, ३ भरने तक डालें। ५ में बचे ४। ४. कोड में अवस्थाएँ (a, b) बनाओ और छह संचालन पर बीएफएस चलाओ अगर रास्ता अपने आप चाहिए। ५. सामान्यतः: जब d % gcd(m, n) == 0 और d कम से कम एक जग में समाए, तब हल योग्य।

अगर बोर्ड पर (0,0) ... (3,4) तालिका घुमा सको, बिना अटके "बेज़ू" कह सको, और २४-अवस्था बीएफएस स्केच कर सको, तो समस्या ६.५ तुम्हारी है।

---

श्रृंखला

• गाइड: सीटीसीआई श्रृंखला गाइड
• पिछला: त्रिभुज पर चींटियाँ
• अगला: नीली आँखों वाला द्वीप