# LintCode: Coin Problem

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.
```
```Give n=50, m=5, return 3.

50-5=45
Ming retrieved two 20 and one 5.
```

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
}
```

Share It, If You Like It.