Coin Problem

Similar Problems:

Ming is a salesman. After the customer bought something in his place and paid Ming a certain amount of money, Xiao Ming needs to return the extra money to the guest. The guest paid Xiao Ming n money, the price of Xiao Ming’s commodity was m money, and the denomination that Xiao Ming can return to the guests can only be a combination of [100, 50, 20, 10, 5, 2, 1]. Now Xiao Ming wants to minimize the sum of the number of banknotes, please return to this minimum.

1 <= m <= n <= 1000000000

Example

Give n=100, m=29, return 3. 100-29=71 Ming retrieved one 50, one 20 and one 1. So the answer is 3.

Give n=50, m=5, return 3. 50-5=45 Ming retrieved two 20 and one 5. So the answer is 3.

Github: code.dennyzhang.com

Credits To: lintcode.com

Leave me comments, if you have better ways to solve.

- Solution:

// Blog link: https://code.dennyzhang.com/coin-problem // Basic Ideas // Complexity: Time O(1), Space O(1) /** * @param n: The guest paid * @param m: the price * @return: the sum of the number of banknotes */ func coinProblem (n int, m int) int { res := 0 num := n-m for _, v := range []int{100, 50, 20, 10, 5, 2, 1} { for num >= v { res += int(num /v) num %= v } } return res }