Minimum Number of Coins
Basic Greedy Problems DSA practice problem on Onlearn.
Difficulty: medium.
Topics: What is the minimum number of coins/notes needed to make change for a given value V using Indian currency denominations?, Greedy Algorithm, Arrays, Time Complexity, Space Complexity, Loops, greedy algorithm, space complexity, dynamic programming, time complexity analysis, Coin Change Problem.
Problem Statement Given a value V, if we want to make a change for V Rs, and we have an infinite supply of each of the denominations in Indian currency, i.e., we have an infinite supply of { 1, 2, 5, 10, 20, 50, 100, 500, 1000} valued coins/notes, what is the minimum number of coins and/or notes needed to make the change. Examples: Example 1: Input: V = 70 Output: 2 Explanation: We need a 50 Rs note and a 20 Rs note. Example 2: Input: V = 121 Output: 3 Explanation: We need a 100 Rs note, a 20 Rs note and a 1 Rs coin.