सभी चुनौतियाँ
मध्यम 1 हल किया गया 100.0% स्वीकृति

सिक्का संयोजन गिनें

निर्दिष्ट सिक्का मूल्यों के असीमित सिक्कों से किसी राशि को बनाने के तरीकों की गिनती करें।

आप क्या सीखेंगे

  • क्रम नहीं, संयोजन गिनना
  • बाहरी लूप में सिक्कों पर चलना
  • तरीकों का 1D DP ऐरे बनाना

समस्या

प्रत्येक दिए गए सिक्का मूल्य का कोई भी संख्या में उपयोग करके राशि को ठीक-ठीक बनाएं। संयोजनों की गिनती करें, क्रम की नहीं: यदि दो व्यवस्थाओं में प्रत्येक सिक्के की संख्या समान है, तो वे एक ही तरीका मानी जाएंगी। सभी सिक्का मूल्य अलग और धनात्मक हैं।

coin_sums(amount, coins) को लागू करें।

इनपुट

amount: वह कुल राशि जिसे बनाना है।

coins: उपलब्ध अलग-अलग सिक्का मूल्य।

आउटपुट

संयोजनों (क्रम रहित) की संख्या लौटाएं।

सीमाएँ

0 ≤ amount ≤ 200। 0 से 10 तक अलग-अलग सिक्का मूल्य हो सकते हैं, प्रत्येक 1 से 200 के बीच। सभी गिनतियां signed 64-bit में समा जाती हैं। राशि 0 के लिए एक ही तरीका है: कोई सिक्का न चुनें।

उदाहरण

उदाहरण 1
इनपुट:
amount = 4
coins = [1, 2]

अपेक्षित आउटपुट:
expected = 3
इनपुट:
long long amount = 4;
std::vector<long long> coins = {1, 2};

अपेक्षित आउटपुट:
long long expected = 3;
इनपुट:
long amount = 4;
long[] coins = new long[] {1, 2};

अपेक्षित आउटपुट:
long expected = 3;

व्याख्या

संयोजन हैं: चार 1 वाले, दो 1 और एक 2 वाला, तथा दो 2 वाले।

उदाहरण 2
इनपुट:
amount = 3
coins = [2]

अपेक्षित आउटपुट:
expected = 0
इनपुट:
long long amount = 3;
std::vector<long long> coins = {2};

अपेक्षित आउटपुट:
long long expected = 0;
इनपुट:
long amount = 3;
long[] coins = new long[] {2};

अपेक्षित आउटपुट:
long expected = 0;

व्याख्या

2 मूल्य वाले सिक्कों का कोई भी योग हमेशा सम होगा, इसलिए 3 बनाना असंभव है।

कैसे हल करें

पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।

संकेत 1

Coins का order matter नहीं करता, इसलिए combinations को denomination के हिसाब से count करो, permutation के हिसाब से नहीं।

संकेत 2

हर amount के लिए ways को incrementally build करो, ताकि हर coin सभी reachable totals में योगदान दे सके।

संकेत 3

Amount zero को ध्यान से handle करो, क्योंकि उसका हमेशा एक valid way होता है: कोई coin नहीं चुनना।

अपेक्षित जटिलता

समय O(amount × number_of_coins), अतिरिक्त स्थान O(amount)

संदर्भ

यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।

हर कोडर का सबसे अच्छा पास हुआ समाधान। तेज़, कम मेमोरी वाले और बेहतर रेटिंग वाले समाधान ऊपर रहते हैं।

# कोडर भाषा समय मेमोरी AI रिव्यू समाधान
1 ННикита Python 811 ms - 5/5 कोड देखें

दूसरों से सीखें

समुदाय समाधान

स्पॉइलर अलर्ट: नीचे 1 पूरा समाधान पहले खुद हल करने की कोशिश करें। आप फिर भी अन्य डेवलपर्स का कोड और AI समीक्षा देख सकते हैं। चर्चा में शामिल होने के लिए साइन इन करें और चुनौती हल करें।