Greedy Algorithm For Ninja And The Coins

Easy

0/40

Contributed by

4 upvotes

Asked in companies

Problem statement

Ninja went to the toffee shop, and he purchased some toffies worth 'V' cents. Ninja has an unlimited supply of coins of 1, 2, 5, 10, 20, 50, 100, 500, and 1000 cents. Now Ninja wants to know the minimum number of coins he needs to pay to the shopkeeper.

Your task is to find the minimum number of coins Ninja needs to pay to the shopkeeper so as to pay 'V' cents to him.

Note: You have to solve this problem using the greedy approach.

Example:

Input: 'V' = 60
Output: 2

Ninja need to pay two coins only 50 + 10 = 60

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line of input contains an integer 'T', denoting the number of test cases. 

Each test case will contain only one integer 'V' on a separate line.

Output format :

For each test case, print the minimum number of coins Ninja needs to pay to the shopkeeper.

Output for each test case will be printed in a separate line.

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= ‘T’ <= 10
1 <= 'V' <= 10^5
Time Limit: 1sec

Sample Input 1 :

2
70
50

Sample Output 1 :

2
1

Explanation Of Sample Input 1 :

For the first test case, Ninja need to pay two coins, only 50 + 20 = 70

For the second test case, Ninja needs to pay only one coin of 50 cents.

Sample Input 2 :

2
121
100

Sample Output 2 :

3
1

Hint 1

Can we start distributing coins greedily by greater value?

Approaches (1)

Approach 1

Greedy Solution

Approach: We will first take coins with a greater value for this problem. This will reduce the total number of coins. We will start from the largest possible coin and keep adding coins till the remaining value is not zero.

Algorithm :

Initialize the vector 'coins' and push the following integers in it.
- 1, 2, 5, 10, 20, 50, 100, 500, 1000
Sort the 'coins'.
Initialize the variable 'count' by 0.
Loop over the 'coins' with the variable 'i' from the last position.
- Run a while loop till 'V' >= 'coins[i]'.
  - Update 'V' with 'V - coins[i]'.
  - Increment the 'count'.
Return 'count'.

Time Complexity

O(V), Where 'V' is the given input integer.

As we are iterating till the ‘V’ is zero hence the time complexity will be O(V)

Space Complexity

O(1)

As we are using the constant extra space, the space complexity will be O(1)

(100% EXP penalty)

Greedy Algorithm For Ninja And The Coins

Console