FLOW005 - Editorial

editorial
1

Problem Link - Smallest Numbers of Notes Practice Problem in 500 to 1000 difficulty problems

Problem Statement:

Given a currency system with six denominations of notes: Rs. 1, Rs. 2, Rs. 5, Rs. 10, Rs. 50, Rs. 100, you need to find the smallest number of notes that combine to give a sum N for each test case.

Approach:

  • Greedy Algorithm:
    • The approach should be greedy because we want to use the highest denomination first to minimize the total number of notes.
    • Start by trying to use as many Rs. 100 notes as possible, then Rs. 50 notes, and so on, until we reach Rs. 1.
  • Steps:
    • For each test case:
      1. Start with the largest denomination (Rs. 100) and divide N by the denomination to get the maximum number of notes for that denomination.
      2. Subtract the equivalent amount from N and move to the next smaller denomination.
      3. Repeat until N becomes 0.
    • The number of notes used for each denomination should be added together to get the total number of notes for that test case.
  • Constraints:
    • Since N can be as large as 1,000,000, the solution needs to be efficient. A greedy approach works in this case, as it guarantees an optimal solution.

Complexity:

  • Time Complexity: O(1) as the loop only runs six times because of the number of elements or currency note in the array.
  • Space Complexity: O(1) No extra space is needed.