Quarters, Dimes, Nickels and Pennies Question
Q. Given a dollar amount, calculate the least amount of coins that would be necessary to fulfill the amount?
This was a question that I was asked at an interview with a company recently and it revolved around finding a method that was reasonably fast to solve the issue.
The best approach of this problem is the quotient and remainder concept. That is, by dividing with the highest denomination and obtaining the quotient as the number for that denomination and moving down the line with the remainder as the new dividend.
For instance, let’s say the dollar amount for the question was “$34.66”.
With this approach:
Step 1: Divide “34.66” by “0.25” giving quotient as “138” and remainder as “0.16”.
Step 2: New Dividend = “0.16” (remainder from step 1). Divide “0.16” by the next highest denomination, which is “0.10” giving quotient as “1” and remainder as “0.06”.
Step 3: New Dividend = “0.06” (remainder from step 2). Divide “0.6” by the next highest denomination, which is “0.05” giving the quotient as “1” and remainder as “0.01”.
Step 4: New Dividend = “0.01” (remainder from step 3). Divide “0.01” by the last denomination available, which is “0.01” giving the quotient as “1” and the remainder as “0”.
THE ANSWER FOR THE EXAMPLE IS: 138 Quarters, 1 Dime, 1 Nickel and 1 Penny.
This step by step procedure could be applied to any dollar amount however high and the answer can be obtained in the same four steps.
Let’s look at a variation of this problem where one of the coins are of different values than in circulation
Updated Q: Given a dollar amount, calculate the least amount of coins that would be necessary to fulfill the amount from only the values $0.25, $0.15, $0.01?
Let’s apply the method from first question, i.e, dividing by highest to lowest of denomination for an example, let’s say “$0.30”.
Step 1: Divide “0.30” by “0.25” to give the quotient “1” and remainder of “0.05”.
Step 2: New Dividend = “0.05” (remainder from step 1). Divide “0.05” by the next highest denomination, which is “0.15" to give the quotient “0” and remainder of “0.05”.
Step 3: New Dividend = “0.05” (remainder from step 1). Divide “0.05” by the next highest denomination, which is “0.01” to give the quotient “5” and remainder of “0”.
THE ANSWER FOR THE EXAMPLE USING IS: 1 coin of $0.25 and 5 coins of $0.01
Total Coins: 6 coins
Alternate Answer: 2 coins of $0.15
Note that in this variation of the problem, the approach from the first example fails to achieve the solution which is to get the minimum combination of coins of different value.
The first example uses the greedy solution approach which gets you a solution but not always the minimum number of coins. A different approach would be to come up with all combinations of the coins for a dollar amount and calculate the total coins used and find the minimum number of coins involved. The complexity of this algorithm ends up being exponential with the number of coin types involved.
We can definitely come up with an algorithm with a lower complexity than that.
Imagine the coin structure as a tree where at the root is the dollar amount and each of the branches is a coin. The idea is to build the solution from top to bottom to reach different viable solutions and look the height. For instance, do the greedy approach and set that branch as a baseline for the height and explore other branches of the tree and discard any branches larger than the baseline and update the baseline if a shorter path is discovered. With this approach, the complexity would be polynomial at the worst than the exponential in the method of calculating all possible outcomes.
