103 — Minimum Coins Basic¶

এই level-এর প্রথম problem, আর এটা শুরুই হচ্ছে একটা ধাক্কা দিয়ে — greedy এখানে কখনো ঠিক, কখনো ডাহা ভুল! ভয় পেও না, বরং উপভোগ করো; কারণ greedy-র fail case নিজের চোখে দেখলে বাকি 9টা problem-এ তুমি অনেক সাবধান চোখ নিয়ে ঢুকবে। ধীরে পড়ো, {1, 3, 4}-এর গল্পটা যেন গেঁথে যায়।

Source¶

Original source: Classic exercise (greedy fails on {1, 3, 4} — নিজে দেখাও)
Platform: Classic exercise / Coin change-এর পরিচিত শিক্ষামূলক রূপ — —
Topic: Greedy math tricks → canonical coin system, counterexample শিকার
Difficulty: Easy
Pattern: canonical greedy (বড় coin আগে নাও — কিন্তু প্রমাণসহ)
Basic idea inherited from: — (greedy level-এর শিকড়, এটাই প্রথম)

1. Problem in simple words¶

তোমার কাছে কয়েক রকম মূল্যের coin আছে — যেমন {1, 2, 5, 10} টাকা। প্রতিটা coin তুমি যতবার খুশি ব্যবহার করতে পারো (unlimited supply)। একটা নির্দিষ্ট amount (যেমন 27 টাকা) ঠিক বানাতে হবে — প্রশ্ন: সবচেয়ে কম কয়টা coin লাগবে?

দুটো ছোট কথা মনে রাখো:

প্রতিটা coin বারবার নেওয়া যায়
কখনো amount বানানোই অসম্ভব হতে পারে (যেমন শুধু {2} দিয়ে 3 বানানো যায় না) — তখন উত্তর "অসম্ভব"

দেখতে সহজ, কিন্তু এর ভেতরেই লুকিয়ে আছে greedy-র সবচেয়ে বিখ্যাত ফাঁদ।

2. What is the math idea?¶

মূল প্রশ্ন: locally লোভী choice (সবচেয়ে বড় coin আগে নাও) কি সবসময় globally সেরা?

উত্তর: না — এটা নির্ভর করে coin set-এর গঠনের উপর।

Canonical system (যেমন আসল টাকার নোট: 1, 2, 5, 10, 20, 50, 100) — এখানে greedy ঠিক উত্তর দেয়
Arbitrary system (যেমন {1, 3, 4}) — এখানে greedy ভুল করতে পারে; তখন DP লাগে (যেটা পরে level 12-এ আসবে)

তাই এই problem আসলে একটা greedy algorithm আর একটা সাবধানবাণী — দুটো একসাথে।

3. Which basic idea does this inherit from?¶

এটা greedy level-এর একদম প্রথম problem, তাই আগের কোনো greedy problem-এর কাঁধে দাঁড়ায় না (inherited from: —)।

বরং এটাই বাকি সব greedy-র জন্য সবচেয়ে জরুরি অভ্যাসটা শেখায়: greedy idea পেলে আগে counterexample খোঁজো। concept-notes-এ যে নিয়ম পড়েছ — "5 মিনিট counterexample খুঁজে না পেলে তবে exchange argument দিয়ে প্রমাণের চেষ্টা" — তার প্রথম হাতে-কলমে প্রয়োগ এখানেই। % (modulo) আর integer division // — এই দুই tool level 0 থেকেই চেনা, সেগুলোই এখানে greedy-র হাতিয়ার।

4. Real-life analogy¶

ভাবো তুমি দোকানে খুচরো ফেরত দিচ্ছ। স্বাভাবিকভাবেই তুমি সবচেয়ে বড় নোটটা আগে দাও — 27 টাকা দিতে হলে আগে 20, তারপর 5, তারপর 2। এই "বড়টা আগে" সহজাত অভ্যাসটাই greedy।

আসল টাকার সিস্টেমে এটা কাজ করে বলেই আমরা রোজ এভাবে খুচরো দিই। কিন্তু কল্পনা করো এক অদ্ভুত দেশ যেখানে শুধু {1, 3, 4} টাকার coin আছে। সেখানে 6 টাকা দিতে গিয়ে "বড়টা আগে" করলে তুমি 4 + 1 + 1 = 3টা coin দেবে — অথচ 3 + 3 = 2টা coin-এই কাজ হতো! সেই দেশে তোমার অভ্যাস তোমাকে ঠকাবে।

5. Visual explanation¶

আগে canonical system-এ greedy কেমন সুন্দর কাজ করে দেখো:

amount = 27,  coins = {10, 5, 2, 1}  (বড় থেকে ছোট)

27 │ 10 নাও → বাকি 17   (count = 1)
17 │ 10 নাও → বাকি 7    (count = 2)
 7 │  5 নাও → বাকি 2    (count = 3)
 2 │  2 নাও → বাকি 0    (count = 4)  ✓
                         মোট 4টা coin

এবার সেই কুখ্যাত fail case — {1, 3, 4} দিয়ে 6:

greedy:   6 → 4 নাও (বাকি 2) → 1 (বাকি 1) → 1 (বাকি 0)   = 3টা coin
optimal:  6 → 3 নাও (বাকি 3) → 3 (বাকি 0)                 = 2টা coin  ✓

          বড় coin (4) নেওয়াটা লোভনীয় ছিল,
          কিন্তু বাকি 2 গড়তে দুটো 1 লাগল — ভবিষ্যৎ নষ্ট হলো!

লক্ষ করো — greedy কোনো ভুল হিসাব করেনি, প্রতি step-এ নিয়ম মেনেই বড়টা নিয়েছে। তবু হেরে গেল। এটাই greedy-র বিপদ।

6. Example input and output¶

amount, coins          ->  output  (ব্যাখ্যা)
---------------------------------------------------------
27, {10, 5, 2, 1}      ->  4       (10+10+5+2)
6,  {1, 2, 5}          ->  2       (5+1)        canonical, greedy ঠিক
0,  {1, 5}             ->  0       (কিছুই লাগে না)
3,  {2}                ->  -1      (অসম্ভব)
6,  {1, 3, 4}          ->  greedy দেয় 3, কিন্তু সত্যিকারের min = 2  ✗

শেষ line-টাই এই note-এর হৃদয় — canonical system-এ আমরা greedy-র উত্তরে বিশ্বাস করি, arbitrary system-এ করি না।

7. Brute force thinking¶

"সত্যিকারের" minimum (যেকোনো coin set-এর জন্য সঠিক) বের করতে সবচেয়ে সরল চিন্তা — সব সম্ভাবনা চেষ্টা করো। প্রতিটা coin বেছে নাও, বাকি amount-এর জন্য আবার একই প্রশ্ন করো (recursion), আর সবচেয়ে কম coin-এর path টা রাখো:

def min_coins_brute(amount, coins):
    if amount == 0:
        return 0
    best = float("inf")
    for c in coins:
        if c <= amount:
            sub = min_coins_brute(amount - c, coins)
            if sub + 1 < best:
                best = sub + 1
    return best

এটা সব coin set-এ ঠিক উত্তর দেয় — কারণ এটা কোনো শর্টকাট নেয় না, প্রতিটা পথ দেখে। তাই আমরা এটাকে "সত্য" হিসেবে ব্যবহার করে greedy-কে যাচাই করতে পারব।

8. Why brute force may be slow¶

এই recursion প্রতিটা step-এ প্রতিটা coin চেষ্টা করে, তাই একই sub-amount বারবার গণনা হয় — গাছটা exponential-ভাবে ফাঁপে। amount একটু বড় হলেই (যেমন 60-70) এটা অসহনীয় ধীর হয়ে যায়।

amount = 30, coins = {1, 3, 4} হলে recursion tree বিশাল —
একই amount (যেমন 10) বহুবার আলাদা পথে গণনা হয়।

brute force : exponential (ধীর) — কিন্তু সব set-এ সঠিক
greedy      : O(coins) প্রায় তাৎক্ষণিক — কিন্তু শুধু canonical-এ সঠিক
DP          : O(amount × coins) — সব set-এ সঠিক ও দ্রুত (পরে level 12)

মাঝখানের সমাধান DP — কিন্তু সেটা পরের গল্প। এখন আমরা greedy আর তার সীমা বুঝছি।

9. Better thinking¶

Canonical system ধরে নিলে greedy অসাধারণ দ্রুত: coins বড় থেকে ছোট sort করো; প্রতিটা coin যতবার সম্ভব নাও (amount // c বার), তারপর বাকি অংশ (amount % c) নিয়ে এগোও।

def min_coins_greedy(amount, coins):
    coins = sorted(coins, reverse=True)
    count = 0
    for c in coins:
        count += amount // c
        amount %= c
    return count if amount == 0 else -1

Greedy choice: প্রতি step-এ amount-এর চেয়ে ছোট/সমান সবচেয়ে বড় coin-টা নাও।

কেন কাজ করে (canonical-এ, এক লাইন): canonical system-এ সবচেয়ে বড় coin c না নিলে, তার জায়গা ছোট coin দিয়ে ভরাট করতে হয় — আর সেই ছোট coin গুলোকে সবসময় কম সংখ্যায় একটা c দিয়ে বদলে (exchange) দেওয়া যায়, তাই বড়টা নেওয়া কখনো খারাপ হয় না। (Arbitrary system-এ ঠিক এই exchange-টাই ভেঙে পড়ে — {1, 3, 4}-এ দুটো 1-কে এক 4 দিয়ে বদলালে বাকি অংশ গড়া কঠিন হয়ে যায়।)

10. Thinking tweak¶

আসল "আহা!" এখানে উল্টো — শেখার জিনিসটা code নয়, সন্দেহ:

"Greedy লিখলাম মানেই হয়ে গেল না — coin set টা canonical তো? একটা ছোট counterexample চালিয়ে দেখি।"

{1, 3, 4} দিয়ে 6 — এই এক লাইনের পরীক্ষাটাই brute force-এর উত্তরের সাথে greedy মিলিয়ে দেখায় ওরা আলাদা। এই "আগে counterexample খুঁজি" reflex-টাই পুরো greedy level-এর সবচেয়ে দামি tweak। code-এ আমরা তাই greedy আর brute দুটোই রেখেছি, আর assert দিয়ে দেখিয়েছি কোথায় মেলে, কোথায় মেলে না।

11. Step-by-step dry run¶

{1, 3, 4} দিয়ে amount = 6 — greedy কীভাবে এগোয়:

step	বর্তমান amount	বাছাই coin	`amount // c`	নতুন amount (`% c`)	মোট count
1	6	4	1	6 % 4 = 2	1
2	2	3	0	2 % 3 = 2	1
3	2	1	2	2 % 1 = 0	3

greedy থামল count = 3-এ। এবার brute force (min_coins_brute(6, [1,3,4])):

6 = 3 + 3        → 2টা coin  ✓ (সত্যিকারের minimum)
greedy দিল 3, brute দিল 2 → মেলে না ⇒ এই set canonical নয়!

একই amount, দুই উত্তর — চোখের সামনে greedy-র সীমা ধরা পড়ল।

12. Python solution¶

def min_coins_greedy(amount, coins):
    """বড় coin আগে — canonical system-এ সঠিক, নাহলে ভুল হতে পারে।"""
    coins = sorted(coins, reverse=True)
    count = 0
    for c in coins:
        count += amount // c
        amount %= c
    return count if amount == 0 else -1


def min_coins_brute(amount, coins):
    """সব পথ দেখে সত্যিকারের minimum — সব set-এ সঠিক, কিন্তু ধীর।"""
    if amount == 0:
        return 0
    best = float("inf")
    for c in coins:
        if c <= amount:
            sub = min_coins_brute(amount - c, coins)
            if sub + 1 < best:
                best = sub + 1
    return best


# --- ছোট test (সব pass করা উচিত) ---

# canonical system-এ greedy == সত্যিকারের minimum
assert min_coins_greedy(27, [10, 5, 2, 1]) == 4          # 10+10+5+2
assert min_coins_greedy(6, [5, 2, 1]) == 2               # 5+1
assert min_coins_greedy(0, [1, 5]) == 0                  # কিছুই লাগে না
assert min_coins_greedy(3, [2]) == -1                    # অসম্ভব

# canonical-এ greedy আর brute একমত (ছোট amount-এ যাচাই, brute ধীর বলে)
for amt in range(0, 21):
    assert min_coins_greedy(amt, [10, 5, 2, 1]) == min_coins_brute(amt, [10, 5, 2, 1])

# কুখ্যাত fail case: {1, 3, 4} দিয়ে 6
assert min_coins_greedy(6, [1, 3, 4]) == 3               # greedy ভুল করে 3 দেয়
assert min_coins_brute(6, [1, 3, 4]) == 2                # সত্যিকারের minimum 2
assert min_coins_greedy(6, [1, 3, 4]) != min_coins_brute(6, [1, 3, 4])   # মেলে না!

print("canonical 27:", min_coins_greedy(27, [10, 5, 2, 1]))   # 4
print("{1,3,4} greedy 6:", min_coins_greedy(6, [1, 3, 4]))    # 3
print("{1,3,4} true   6:", min_coins_brute(6, [1, 3, 4]))     # 2
print("সব test pass!")

13. Line-by-line explanation¶

coins = sorted(coins, reverse=True)

greedy-র প্রথম শর্ত — বড় coin আগে। তাই descending sort।

count += amount // c
amount %= c

এই দুই লাইনই greedy-র হৃদয়। amount // c বলে দেয় এই coin সর্বোচ্চ কতবার নেওয়া যায়, আর amount %= c বাকি অংশ রাখে পরের (ছোট) coin-এর জন্য। এক loop-এই সব coin শেষ।

return count if amount == 0 else -1

সব coin শেষেও amount বাকি থাকলে এই set দিয়ে বানানো অসম্ভব → -1।

min_coins_brute হলো আমাদের "সত্যের পরিমাপক" — প্রতিটা coin চেষ্টা করে recursion-এ বাকিটা সমাধান করে সবচেয়ে কম path রাখে। ধীর, কিন্তু সব set-এ নির্ভুল, তাই greedy-কে যাচাই করতে আদর্শ।

বাকি assert লাইনগুলো নিজেরাই চেক করছে: canonical-এ greedy আর brute সমান (range(0, 40) লুপে সব মিলিয়ে দেখা), আর {1, 3, 4}-এ ওরা আলাদা — এই অমিলটাই আমরা assert দিয়ে প্রমাণ করছি।

14. Output walkthrough¶

চালালে ছাপবে:

canonical 27: 4
{1,3,4} greedy 6: 3
{1,3,4} true   6: 2
সব test pass!

প্রথম line — canonical টাকায় greedy 27-কে 4 coin-এ ভাঙল (সঠিক)। পরের দুই line — একই amount 6-এ greedy দিল 3, কিন্তু সত্যিকারের minimum 2। সব assert চুপচাপ pass করেছে (assert fail করলেই কেবল চিৎকার করত), তাই শেষে সব test pass!।

15. Time complexity¶

Greedy: O(k log k) — k = coin সংখ্যা, মূল খরচ sorting; তারপর এক pass O(k)। amount-এর আকারের সাথে কাজ বাড়ে না।
Brute force: exponential — প্রতিটা step-এ k-টা শাখা, গভীরতা amount পর্যন্ত; তাই amount বাড়লে দ্রুত অসহনীয়।

16. Space complexity¶

Greedy: O(1) বাড়তি (sorting বাদ দিলে) — শুধু গুটিকয় variable।
Brute force: O(amount) — recursion stack-এর গভীরতা amount পর্যন্ত যেতে পারে।

17. Common mistakes¶

প্রমাণ ছাড়া greedy বিশ্বাস করা — সবচেয়ে বড় ভুল। coin set canonical কিনা না দেখে greedy চালালে arbitrary set-এ ভুল উত্তর আসবে। আগে অন্তত একটা ছোট counterexample খোঁজো।
{1, 3, 4} counterexample ভুলে যাওয়া — interview-তে "greedy কেন সবসময় কাজ করে না" প্রশ্নের one-shot উত্তর এটাই; না দেখে লিখতে পারা চাই।
Coin sort না করা — descending sort না করলে greedy logic-ই ভেঙে পড়ে; বড়টা আগে না নিলে এটা greedy-ই নয়।
অসম্ভব case না সামলানো — amount বানানো না গেলে -1 (বা "অসম্ভব") ফেরত দিতে ভুলো না; নাহলে ভুল count চলে যাবে।
DP-র সাথে গুলিয়ে ফেলা — মনে রেখো: arbitrary set-এ সঠিক minimum চাইলে greedy নয়, DP লাগে — সেটা পরে level 12-এ।

18. Harder problems that inherit this idea¶

LeetCode — Coin Change (https://leetcode.com/problems/coin-change/) — যেখানে greedy ভেঙে পড়ে, সেখানে DP দিয়ে যেকোনো coin set-এ সঠিক minimum বের করা।
LeetCode — Coin Change II (https://leetcode.com/problems/coin-change-ii/) — কত ভাবে amount বানানো যায়, সেই counting DP।
LeetCode — Lemonade Change (https://leetcode.com/problems/lemonade-change/) — এখানে greedy আবার ঠিকঠাক কাজ করে (canonical-ঘেঁষা change-making), তুলনা করার ভালো সঙ্গী।

19. Pattern learned¶

Canonical greedy with counterexample check — বড় coin আগে নাও, কিন্তু আগে নিশ্চিত হও coin set canonical কিনা; না হলে greedy ভুল করে, DP লাগে। বড় শিক্ষা: greedy লিখেই থেমো না, একটা ছোট counterexample চালিয়ে যাচাই করো।

20. Final summary¶

ভবিষ্যতের আমাকে এক লাইনে: "min coins = বড় coin আগে (greedy) — কিন্তু শুধু canonical system-এ সঠিক; {1, 3, 4} দিয়ে 6-এ greedy দেয় 3, সত্যি 2। greedy দেখলেই প্রথম প্রশ্ন: counterexample আছে কি?"

পরের ধাপ → 104 — Jump Game (এবার greedy যেখানে প্রমাণসহ কাজ করে — furthest reach)।

ফিরে দেখা: এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; কোনো problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" এমন দাবি নয় — বরং "common interview pattern" / "Google-style pattern"।