Find minimum number of coins - Leetcode

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

Explaination: We need a 50 Rs note and a 20 Rs note.

Example 2:

Input: V = 121

Output: 3

Explaination: We need a 100 Rs note, a 20 Rs note and a 1 Rs coin.

Solution:

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution: Greedy Algorithm

Approach: We will keep a pointer at the end of the array i. Now while(V >= coins[i]) we will reduce V by coins[i] and add it to the ans array.

We will also ignore the coins which are greater than V and the coins which are less than V. We consider them and reduce the value of V by coins[I].

Code:

C++ Code


#include<bits/stdc++.h>


using namespace std;
int main() {
  int V = 49;
  vector < int > ans;
  int coins[] = {1, 2, 5, 10, 20, 50, 100, 500, 1000};
  int n = 9;
  for (int i = n - 1; i >= 0; i--) {
    while (V >= coins[i]) {
      V -= coins[i];
      ans.push_back(coins[i]);
    }
  }
  cout<<"The minimum number of coins is "<<ans.size()<<endl;
  cout<<"The coins are "<<endl;
  for (int i = 0; i < ans.size(); i++) {
    cout << ans[i] << " ";
  }

  return 0;
}

Output:

The minimum number of coins is 5
The coins are
20 20 5 2 2

Time Complexity:O(V)

Space Complexity:O(1)

Java Code


import java.util.*;
public class Main {
  public static void main(String[] args) {

    int V = 49;
    ArrayList < Integer > ans = new ArrayList < > ();
    int coins[] = {1, 2, 5, 10, 20, 50, 100, 500, 1000};
    int n = coins.length;
    for (int i = n - 1; i >= 0; i--) {
      while (V >= coins[i]) {
        V -= coins[i];
        ans.add(coins[i]);
      }
    }
    System.out.println("The minimum number of coins is "+ans.size());
    System.out.println("The coins are ");
    for (int i = 0; i < ans.size(); i++) {
      System.out.print(" " + ans.get(i));
    }

  }
}

Output:

The minimum number of coins is 5
The coins are
20 20 5 2 2

Time Complexity:O(V)

Space Complexity:O(1)

Python Code

if __name__ == '__main__':
    V = 49
    ans = []
    coins = [1, 2, 5, 10, 20, 50, 100, 500, 1000]
    n = 9
    for i in range(n - 1, -1, -1):
        while V >= coins[i]:
            V -= coins[i]
            ans.append(coins[i])
    print("The minimum number of coins is", len(ans))
    print("The coins are")
    for i in range(len(ans)):
        print(ans[i], end=" ")

Output:

The minimum number of coins is 5
The coins are
20 20 5 2 2

Time Complexity:O(V)

Space Complexity:O(1)

Special thanks to P.C.Bhuvaneshwari and Sudip Ghosh for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article