খুচরা

নির্দেশনা

গ্রাহককে ফেরত দেওয়ার জন্য সবচেয়ে কম সংখ্যক কয়েন ঠিকভাবে বের করুন, যাতে সেই কয়েনগুলোর মানের যোগফল ঠিক পরিমাণ খুচরা টাকার সমান হয়।

উদাহরণ

• ইনপুট 15 এবং কয়েনের সেট [1, 5, 10, 25, 100] হলে রিটার্ন আসা উচিত একটি নিকেল (5) আর একটি ডাইম (10), অর্থাৎ [5, 10]
• ইনপুট 40 এবং কয়েনের সেট [1, 5, 10, 25, 100] হলে রিটার্ন আসা উচিত একটি নিকেল (5), একটি ডাইম (10) আর একটি কোয়ার্টার (25), অর্থাৎ [5, 10, 25]

এজ কেস

• আপনার অ্যালগরিদম কি যেকোনো দেওয়া কয়েনের সেটের জন্য কাজ করে?
• ঋণাত্মক খুচরা টাকা চাওয়া কি সম্ভব?
• সবচেয়ে ছোট কয়েনের মানের চেয়েও ছোট কোনো খুচরা টাকার পরিমাণ কি চাওয়া যায়?

---

সূত্র

Software Craftsmanship - Coin Change Kata