360. Greedy Algorithm to Find Minimum Number of Coins

Using the standard Indian currency denominations {1, 2, 5, 10, 20, 50, 100, 500, 2000}, find the minimum number of coins/notes needed to make up a given amount by always using as many of the current largest denomination as possible before moving to the next smaller one.

Input: A single line contains one integer, the amount to make change for. Output: Print a single integer - the minimum number of coins/notes needed.

1 <= amount <= 10^9

This is one of the few coin-change scenarios where greedy is PROVABLY correct - real-world currency systems (like this one) are typically deliberately designed with this greedy-friendly property, unlike arbitrary denomination sets used in some algorithm problems specifically to break greedy.

Find the minimum number of coins/notes needed to make up an amount, using standard Indian currency denominations. Brute force: Try every possible combination of denominations summing to the target and find the one using the fewest coins - this is the general 'coin change' problem, solvable with DP for ARBITRARY denomination sets, but unnecessary here. Optimised: For this SPECIFIC denomination set (1,2,5,10,20,50,100,500,2000), the greedy 'take the largest fitting denomination first' strategy happens to always produce the true minimum coin count - a special property of this particular set of denominations (not true for arbitrary denomination sets in general).

Recursively try, at each step, subtracting every denomination that is not larger than the remaining amount and recursing on what's left, taking the minimum number of coins over all branches that reach exactly zero. This explores every possible way of expressing the amount as a sum of denominations and is guaranteed correct for any coin system, but without memoization it repeats the same remaining-amount subproblems many times and grows exponentially. Time: O(numDenominations^amount) roughly (exponential) Space: O(amount)

Sort the denominations descending (or rely on the given descending canonical order), and repeatedly take as many of the current largest denomination as fit into the remaining amount, subtract that, and move to the next smaller denomination, continuing until the amount reaches zero. This works correctly specifically because the Indian currency denominations {1,2,5,10,20,50,100,500,2000} form a 'canonical' coin system for which the greedy choice is always part of some optimal solution, a property that does not hold for arbitrary denominations, which is why the DP approach exists as a fallback for non-canonical systems. Because it only needs one pass over the fixed small list of denominations rather than an array sized by the amount, it handles amounts up to 10^9 instantly. Time: O(numDenominations) = O(1) Space: O(1)

Use the classic minimum-coin-change dynamic program: dp[i] = minimum coins to make amount i, computed as 1 + min(dp[i - denom]) over every denomination not exceeding i, filled iteratively from 0 up to the target amount. This is correct for any set of denominations, not just this canonical one, and avoids the brute force's repeated recomputation - but with amount up to 10^9, an array of that size is completely infeasible in both time and memory. Time: O(amount * numDenominations) Space: O(amount)

1. Process denominations from LARGEST to smallest. 2. At each denomination, take as many as fit into the remaining amount. 3. Subtract what was taken from the remaining amount and move to the next smaller denomination, repeating until the remaining amount reaches 0.

Time: O(number of denominations) - a small, fixed number of denominations to iterate through, each taking O(1) work. Space: O(1) extra space - just a running remainder and coin count.

amount = 1 (a single 1-rupee coin), and amount up to 10^9 with large multiples of 2000 to confirm the greedy handles big values correctly.

Be ready to explain explicitly WHY greedy works for THIS denomination set but not for an arbitrary one (e.g. denominations {1,3,4} for target 6 - greedy gives 4+1+1=3 coins, but the true optimal is 3+3=2 coins) - this contrast is a classic interview probe testing whether you understand greedy's LIMITS, not just its application.