Minimum US Coins

EasyGreedyMath
Practice This ProblemBattle with This Problem

Description

Given a non-negative integer n cents, return the minimum number of US coins (denominations 25, 10, 5, 1) needed to make exactly n cents. A greedy approach works because of the denomination structure.

Examples

Input:n = 41
Output:4
Explanation:

25 + 10 + 5 + 1 = 4 coins.

Input:n = 0
Output:0
Explanation:

Zero cents needs zero coins.

Input:n = 99
Output:9
Explanation:

3*25 + 2*10 + 0*5 + 4*1 = 9 coins.

Constraints

  • •0 ≤ n ≤ 10⁹

Ready to solve this problem?

Practice solo or challenge other developers in a real-time coding battle!