# Greedy Algorithm For Ninja And The Coins

Easy
0/40
Contributed by
1 upvote

## 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 )
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
``````
Console