सिक्के: ख़ुर्द-बुर्द बनाने के तरीकों की गिनती (जावा)

टीएल;डीआर

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

कुछ तय मूल्यों के सिक्के अनगिनत हैं। कोई पूछता है: ठीक n पैसे के कितने अलग ढेर बनते हैं? सबसे कम सिक्के नहीं। संयोजनाओं की गिनती। यही क्लासिक सिक्के समस्या है: २५, १०, ५, १ के सिक्के, और एक लक्ष्य राशि।

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

---

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

एक वेंडिंग मशीन सोचो जो सिर्फ २५, १०, ५ और १ लेती है। ठीक ३० पैसे चुकाने हैं। पहले कौन सा सिक्का गिरा, इससे फ़र्क नहीं। तीन दस वाले एक तरीका। एक पच्चीस और एक पाँच दूसरा। छह पाँच वाले तीसरा। स्लॉट में क्रम नया तरीका नहीं बनाता।

अगर क्रम मायने रखता, तीन दस वाले उन्हीं तीन सिक्कों की कई क्रमचय में फूट जाते। इंटरव्यू में लगभग हमेशा संयोजना माँगते हैं: सिक्कों का वही मल्टीसेट एक तरीका।

हर राशि के लिए "कितने तरीके" की छोटी तालिका हर ढेर हाथ से गढ़ने से आसान है। वही तालिका डायनामिक प्रोग्रामिंग है।

---

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

इनपुट: गैर-ऋणात्मक पूर्णांक n (बनाने वाले पैसे)। वैकल्पिक मूल्य सूची; क्लासिक सेट {25, 10, 5, 1}।

आउटपुट: उन सिक्कों की अलग-अलग संयोजनाओं की संख्या जो ठीक n जोड़ती हों। समान मूल्य के सिक्के एक जैसे। हर प्रकार जितने चाहो इस्तेमाल (असीमित आपूर्ति)।

उदाहरण सिक्के {25, 10, 5, 1} के साथ:

न	तरीके (विचार)	गिनती
०	खाली ढेर	१
१	एक पैसा	१
५	पाँच पैसे; एक निकेल	२
१०	नीचे वॉकथ्रू देखो	४
३०	२५/१०/५/१ के कई मिक्स	१८

n = 10 के तरीके (हर पंक्ति एक संयोजना):

10×1
1×5 + 5×1
2×5
1×10

यह ४ है। 5 फिर 5 को उल्टे क्रम से अलग नहीं गिनते; निकेल एक जैसे हैं।

कोड से पहले साफ़ करो:

• संयोजना या क्रमचय? संयोजना (क्रम मायने नहीं)।
• हर मूल्य असीमित? हाँ, जब तक न कहा जाए।
• ways(0) क्या? अक्सर १ (एक खाली संयोजना)। ज़ोर से बोलो।
• ऋणात्मक n? ० लौटाओ, या मान लो n >= 0।
• रिटर्न टाइप? इंटरव्यू आकार के लिए int ठीक; बड़ा n हो तो long का ज़िक्र।
• तय सिक्के या जेनेरिक ऐरे? जेनेरिक ऐरे लिखो; डेमो {25, 10, 5, 1} से।

---

३. पहले सोचो

ब्रूट फ़ोर्स रिकर्शन

एक बार में एक सिक्का प्रकार चुनो ताकि क्रम घुस न पाए। सिक्का इंडेक्स i और बाकी rem पर:

• अगर rem == 0, १ गिनो।
• अगर rem < 0 या प्रकार खत्म, ० गिनो।
• नहीं तो coins[i] की ०, १, २, ... प्रतियाँ आज़माओ, अगले प्रकार पर बचे राशि के साथ रिकर्शन।

हर संयोजना एक बार घूमती है। मेमो बिना धीमा: कई ओवरलैप सबप्रॉब्लम जैसे "इंडेक्स २ से सिक्के और rem = 40"।

मेमो वाला रिकर्शन

(coinIndex, remaining) पर कैश। वही तर्क, काफी तेज़। फिर भी दो आयामों की अवस्था।

नीचे से ऊपर डीपी (इंटरव्यू डिफ़ॉल्ट)

ऐरे ways[0 .. n] बनाओ जहाँ ways[a] मतलब "a जोड़ने वाली संयोजनाओं की संख्या"।

ways[0] = 1
for each coin c in coins:
    for a from c to n:
        ways[a] += ways[a - c]

लूप क्रम क्यों मायने रखता है:

बाहरी लूप	भीतरी लूप	क्या गिनते हो
सिक्के, फिर राशियाँ	ऊपर जैसा	संयोजना (हर मल्टीसेट एक बार)
राशियाँ, फिर सिक्के	लूप अदला-बदली	क्रमचय (क्रम मायने रखता है)

पहली तालिका चाहिए। हर सिक्का पूरी तरह "आने" के बाद अगला आता है, इसलिए सिर्फ क्रम से अलग सीक्वेंस ऐरे में एक ही रास्ते में सिमटती हैं।

एक कदम की समझ: सिक्का c उपलब्ध होने पर, a - c बनाने का हर पुराना तरीका एक और c जोड़कर a बनाने का तरीका बन जाता है। भीतरी लूप ऊपर चढ़ता है, इसलिए एक ही ways ऐरे पर कई c जुड़ सकते हैं।

छोटा वॉकथ्रू: न = १०, सिक्के = [1, 5, 10]

शुरू: ways = [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

सिक्का १ के बाद (सिर्फ पैसे): हर राशि का १ तरीका।

सिक्का ५ के बाद:

• राशि ५: ways[5] += ways[0] → २
• राशि ६: ways[6] += ways[1] → २
• ...
• राशि १०: निकेल वाले तरीके जमा

सिक्का १० के बाद: ways[10] += ways[0] शुद्ध डाइम जोड़ता है। अंत ways[10] = 4।

"न्यूनतम सिक्के" डीपी क्यों नहीं

प्रसिद्ध "सबसे कम सिक्के" समस्या न्यूनतम लंबाई रखती है। यह समस्या गिनती रखती है। नेस्टेड लूप का आकार समान, पुनरावृत्ति अलग:

• मिन: dp[a] = min(dp[a], dp[a - c] + 1)
• वेज़: ways[a] += ways[a - c]

इंटरव्यू में इन्हें दिमाग में मिलाओ मत।

व्हाइटबोर्ड स्केच

१. मूल्य लिखो 25, 10, 5, 1। २. ways[0]=1 बनाओ, बाकी शून्य। ३. छोटे n जैसे १० पर एक-एक सिक्का (मन में) चलाओ। ४. लूप क्रम घेरो (सिक्का बाहर) ताकि क्रमचय में न फिसलो। ५. जेनेरिक मेथड लिखो, क्लासिक ऐरे से कॉल करो।

---

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

/**
 * Number of combinations that sum to n using unlimited coins from denominations.
 * Order does not matter. ways(0) == 1.
 */
int makeChange(int n, int[] coins) {
    if (n < 0) {
        return 0;
    }
    int[] ways = new int[n + 1];
    ways[0] = 1;

    for (int coin : coins) {
        if (coin <= 0) {
            continue; // skip bad denominations if any slip in
        }
        for (int amount = coin; amount <= n; amount++) {
            ways[amount] += ways[amount - coin];
        }
    }
    return ways[n];
}

/** Classic CTCI denominations: quarters, dimes, nickels, pennies. */
int makeChange(int n) {
    return makeChange(n, new int[] {25, 10, 5, 1});
}

रिकर्सिव + मेमो रूप (वही उत्तर)

अगर पहले ऊपर से नीचे माँगे:

int makeChangeMemo(int n, int[] coins) {
    if (n < 0) {
        return 0;
    }
    Integer[][] memo = new Integer[coins.length][n + 1];
    return waysFrom(0, n, coins, memo);
}

private int waysFrom(int index, int remaining, int[] coins, Integer[][] memo) {
    if (remaining == 0) {
        return 1;
    }
    if (index == coins.length) {
        return 0;
    }
    if (memo[index][remaining] != null) {
        return memo[index][remaining];
    }

    int ways = 0;
    int coin = coins[index];
    for (int count = 0; count * coin <= remaining; count++) {
        ways += waysFrom(index + 1, remaining - count * coin, coins, memo);
    }
    memo[index][remaining] = ways;
    return ways;
}

नीचे से ऊपर ऐरे समय दबाव में छोटा लिखना आसान। दोनों जानो।

वॉकथ्रू: न = ५, सिक्के = [1, 5]

कदम	ways[0..5] की अवस्था
आरंभ	[1, 0, 0, 0, 0, 0]
१ के बाद	[1, 1, 1, 1, 1, 1]
५ के बाद	[1, 1, 1, 1, 1, 2]

उत्तर २: पाँच पैसे, या एक निकेल।

न्यूनतम स्मोक टेस्ट

public static void main(String[] args) {
    int[] coins = {25, 10, 5, 1};
    System.out.println(makeChange(0, coins));   // 1
    System.out.println(makeChange(1, coins));   // 1
    System.out.println(makeChange(5, coins));   // 2
    System.out.println(makeChange(10, coins));  // 4
    System.out.println(makeChange(30, coins));  // 18
}

---

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

दृष्टिकोण	समय	अतिरिक्त जगह	नोट
बिना मेमो रिकर्शन	घातांकीय	O(d) स्टैक	d = मूल्यों की संख्या; बहुत धीमा
(इंडेक्स, बाकी) पर मेमो	O(d · n · ...) लूप के अनुसार	O(d · n)	ठीक; ज़्यादा कोड
नीचे से ऊपर ways[]	O(d · n)	O(n)	इंटरव्यू में पसंदीदा
सिर्फ ४ तय सिक्के	O(n)	O(n)	वही आइडिया, d नियत

क्लासिक चार सिक्कों पर समय n में रैखिक। फिर भी O(d · n) बोलो, सामान्य लगे।

---

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

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

• n = 0 → १ लौटाओ (एक खाली संयोजना)। ० नहीं।
• ऋणात्मक n → ०, या इनपुट अस्वीकार।
• सिर्फ पैसे → हर गैर-ऋणात्मक n के लिए ठीक एक तरीका।
• n न बन सके (जैसे सिक्के {2, 4} और n = 3) → ways[n] ० रहता है।
• ऐरे में डुप्लिकेट मूल्य → दोहरी गिनती; अद्वितीय मान मानो, या पहले हटाओ।
• n से बड़ा सिक्का → भीतरी लूप नहीं चलता; नुकसान नहीं।
• पूर्णांक ओवरफ़्लो → बड़े n और कई सिक्कों पर int लपेट सकता है। सीमा बढ़े तो long का ज़िक्र।

आम गलतियाँ:

१. लूप क्रम पलटना और क्रमचय गिनना। तीन पैसे अलग-अलग क्रम में ज़्यादा गिने जाएँगे। २. ways[0] = 0 रखना। फिर हर राशि हमेशा शून्य। ३. बिना ज़रूरत २डी टेबल और इंडेक्स गड़बड़। असीमित सिक्कों की संयोजना के लिए १डी काफी। ४. गिनती की जगह न्यूनतम सिक्के हल करना। अलग पुनरावृत्ति। ५. coins ऐरे बदलना या बिना ज़रूरत सॉर्ट। सॉर्ट नुकसान नहीं, पर संयोजना डीपी को सॉर्ट की ज़रूरत नहीं अगर हर प्रकार एक बार पूरा चलता है।

---

७. दोस्त को समझाने वाला सार

सिक्के पूछते हैं: असीमित २५/१०/५/१ से ठीक n पैसे की कितनी अलग संयोजनाएँ?

१. क्रम मायने नहीं। तीन दस वाले एक तरीका, छह क्रमचय नहीं। २. ways[0] = 1। शून्य पैसे एक तरह बनते हैं: कुछ न लगाना। ३. हर सिक्के पर उस सिक्के से n तक राशि चलाओ और ways[a] += ways[a - c] करो। ४. बाहरी लूप सिक्के: संयोजना। बाहरी राशि: क्रमचय। कौन सा चाहिए, बोलो। ५. समय O(d · n), जगह O(n)। न = १० पर उत्तर ४; क्लासिक सेट पर न = ३० पर १८।

अगर न = १० के लिए ways हाथ से भर सको और लूप क्रम क्रमचय क्यों मारता है समझा सको, समस्या ८.११ तुम्हारी है।

---

सीरीज़

• गाइड: सीटीसीआई सीरीज़ गाइड
• पिछला: पेंट फ़िल
• अगला: आठ रानियाँ