समस्या
एक कैशियर छुट्टे देने के लिए क्वार्टर (25¢), डाइम (10¢), निकल (5¢) और पेनी (1¢) का उपयोग करता है। हमेशा सबसे बड़े ऐसे सिक्के का उपयोग करना जो अभी भी फिट हो सके, इन मूल्यों के लिए सबसे कम सिक्कों की आवश्यकता देता है। यह बताएं कि दिए गए cents के लिए कितने सिक्कों की आवश्यकता होगी।
fewest_coins(cents) को इम्प्लीमेंट करें।
इनपुट
cents: बकाया छुट्टे (सेंट्स में)।
आउटपुट
न्यूनतम आवश्यक सिक्कों की संख्या लौटाएं।
सीमाएँ
0 ≤ cents ≤ 1,000,000
उदाहरण
इनपुट:
cents = 41
अपेक्षित आउटपुट:
expected = 4इनपुट:
long long cents = 41;
अपेक्षित आउटपुट:
long long expected = 4;इनपुट:
long cents = 41;
अपेक्षित आउटपुट:
long expected = 4;व्याख्या
एक क्वार्टर (25), एक डाइम (35), एक निकल (40) और एक पेनी (41): कुल 4 सिक्के।
इनपुट:
cents = 0
अपेक्षित आउटपुट:
expected = 0इनपुट:
long long cents = 0;
अपेक्षित आउटपुट:
long long expected = 0;इनपुट:
long cents = 0;
अपेक्षित आउटपुट:
long expected = 0;व्याख्या
कोई छुट्टे नहीं देने हैं: 0 सिक्के।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
जो सबसे बड़ा coin denomination fit हो, पहले उसे use करें, फिर बचे हुए amount के साथ smaller coins पर जाएँ.
संकेत 2
हर coin type को efficiently count करने के लिए divide और remainders का use करें.
संकेत 3
Exact multiples का ध्यान रखें ताकि गलती से leftover amount न रह जाए.
अपेक्षित जटिलता
समय O(1), अतिरिक्त स्थान O(1)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।