समस्या
आप दिए गए सिक्कों में से कोई भी उपसमूह चुन सकते हैं। प्रत्येक सिक्का अधिकतम एक बार ही इस्तेमाल किया जा सकता है, भले ही एक ही मूल्य के कई सिक्के हों। वह सबसे छोटी धनराशि (सकारात्मक पूर्णांक) ज्ञात करें जिसे कोई भी चयन नहीं बना सकता।
missing_coin_sum(coins) को लागू करें।
इनपुट
coins: उपलब्ध सिक्कों के मूल्य; डुप्लिकेट अलग-अलग सिक्कों को दर्शाते हैं।
आउटपुट
सबसे छोटी सकारात्मक असंभव राशि लौटाएँ।
सीमाएँ
1 ≤ सिक्कों की संख्या ≤ 200,000। प्रत्येक मूल्य 1 और 1,000,000,000 के बीच है।
उदाहरण
इनपुट:
coins = [1, 1, 4]
अपेक्षित आउटपुट:
expected = 3इनपुट:
std::vector<long long> coins = {1, 1, 4};
अपेक्षित आउटपुट:
long long expected = 3;इनपुट:
long[] coins = new long[] {1, 1, 4};
अपेक्षित आउटपुट:
long expected = 3;व्याख्या
राशि 1 और 2 एक-मूल्य वाले सिक्कों से बनती हैं। कोई भी उपलब्ध उपसमूह 3 नहीं बना सकता।
इनपुट:
coins = [2, 3]
अपेक्षित आउटपुट:
expected = 1इनपुट:
std::vector<long long> coins = {2, 3};
अपेक्षित आउटपुट:
long long expected = 1;इनपुट:
long[] coins = new long[] {2, 3};
अपेक्षित आउटपुट:
long expected = 1;व्याख्या
1 बनाने का कोई तरीका नहीं है क्योंकि हर सिक्के का मूल्य कम से कम 2 है।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
Coins को sort करो और smallest से upward सबसे छोटा reachable sum बनाओ.
संकेत 2
अगर अगला coin first unreachable amount से बड़ा है, तो वह amount कभी form नहीं किया जा सकता.
संकेत 3
Duplicates तभी मदद करते हैं जब वे बिना gap के reachable range बढ़ाएँ.
अपेक्षित जटिलता
O(n log n) time, O(1) extra space, excluding sorting implementation details
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।