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.
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
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.