Exact Coin Change Puzzle.
Suppose that you are a sales person at a cash register and you have one purchase to serve before you close. A buyer has to pay X dollars and N cents with bills only (no coins). You have lots of bills of various nomination and limited number of coins: 3 quarters, 9 dimes, 19 nickels, and 4 pennies left in the register. You are required to give the exact change (between 1 and 99 cents) using smallest number of (available) coins.
- Use a single SELECT statement
- The result should return 1 row and 4 columns indicating how many coins of each type to use
- 1 Quarter = 25 cents; 1 Dime = 10 cents; 1 Nickel = 5 cents
Sample result for a change of 63 cents:
Quarters Dimes Nickels Pennies
---------- ---------- ---------- ----------
2 1 0 3
Solution #1: Using Math formula and MODEL clause:
For American coins one can rely on a mathematical formula to get the smallest number of coins for exact change:
Quarters: FLOOR of [Change Amount]/25
Dimes: FLOOR(([Change Amount] – 25*[Quarters])/10)
Nickels: FLOOR(([Change Amount] – 25*[Quarters]-10*[Dimes])/5)
Pennies: [Change Amount] – 25*[Quarters]-10*[Dimes] – 5*[Nickels]
One of the easiest ways to implement this strategy is to employ the MODEL clause:
WITH m AS (
SELECT 63 AS cents
FROM dual
)
SELECT cents "Change",
Q "Quarters",
D "Dimes",
N "Nickels",
P "Pennies"
FROM m
MODEL
DIMENSION BY(0 AS dummy)
MEASURES(
cents,
CAST(0 AS NUMBER(3)) AS Q,
CAST(0 AS NUMBER(3)) AS D,
CAST(0 AS NUMBER(3)) AS N,
CAST(0 AS NUMBER(3)) AS P
)
RULES (
Q[0]=FLOOR(CENTS[0]/25),
D[0]=FLOOR((CENTS[0]-Q[0]*25)/10),
N[0]=FLOOR((CENTS[0]-Q[0]*25-D[0]*10)/5),
P[0]=(CENTS[0]-Q[0]*25-D[0]*10-N[0]*5)
)
Result:
| Change |
Quarters |
Dimes |
Nickels |
Pennies |
| 63 |
2 |
1 |
0 |
3 |
If we want to extend this solution to see the change combinations for all values from 1 to 99, we will need to change the above solution as follows:
WITH m AS (
SELECT LEVEL cents
FROM dual
CONNECT BY LEVEL<=99
)
SELECT cents "Change",
Q "Quarters",
D "Dimes",
N "Nickels",
P "Pennies"
FROM m
MODEL
PARTITION BY(ROWNUM AS rn)
DIMENSION BY(0 AS dummy)
MEASURES(
cents,
CAST(0 AS NUMBER(3)) AS Q,
CAST(0 AS NUMBER(3)) AS D,
CAST(0 AS NUMBER(3)) AS N,
CAST(0 AS NUMBER(3)) AS P
)
RULES (
Q[0]=FLOOR(CENTS[0]/25),
D[0]=FLOOR((CENTS[0]-Q[0]*25)/10),
N[0]=FLOOR((CENTS[0]-Q[0]*25-D[0]*10)/5),
P[0]=(CENTS[0]-Q[0]*25-D[0]*10-N[0]*5)
)
ORDER BY 1
Result:
| Change |
Quarters |
Dimes |
Nickels |
Pennies |
| 1 |
0 |
0 |
0 |
1 |
| 2 |
0 |
0 |
0 |
2 |
| 3 |
0 |
0 |
0 |
3 |
| 4 |
0 |
0 |
0 |
4 |
| 5 |
0 |
0 |
1 |
0 |
| 6 |
0 |
0 |
1 |
1 |
| 7 |
0 |
0 |
1 |
2 |
| 8 |
0 |
0 |
1 |
3 |
| 9 |
0 |
0 |
1 |
4 |
| 10 |
0 |
1 |
0 |
0 |
| … |
… |
… |
… |
… |
| 95 |
3 |
2 |
0 |
0 |
| 96 |
3 |
2 |
0 |
1 |
| 97 |
3 |
2 |
0 |
2 |
| 98 |
3 |
2 |
0 |
3 |
| 99 |
3 |
2 |
0 |
4 |
Solution #2: Using Enhanced Math formula:
It’s easy to see that the MOD function is very handy in determining the number of coins other than quarters (the largest):
WITH a AS (
SELECT 63 cents
FROM dual
)
SELECT a.cents "Change",
FLOOR(a.cents/25) "Quarters",
FLOOR(MOD(a.cents,25)/10) "Dimes",
FLOOR(MOD(MOD(a.cents,25),10)/5) "Nickels",
MOD(MOD(MOD(a.cents,25),10),5) "Pennies"
FROM a
Alternatively, we can see coin combinations for all change amounts from 1 to 99 cents:
WITH a AS (
SELECT LEVEL cents
FROM dual
CONNECT BY LEVEL<100
)
SELECT a.cents "Change",
FLOOR(a.cents/25) "Quarters",
FLOOR(MOD(a.cents,25)/10) "Dimes",
FLOOR(MOD(MOD(a.cents,25),10)/5) "Nickels",
MOD(MOD(MOD(a.cents,25),10),5) "Pennies"
FROM a
ORDER BY a.cents
Solution #3: Using Cartesian Product and Top Record pattern approach:
If we did not know the exact math formula, we could still count on the brute force approach – go over all possible coin permutations (Cartesian product) that sum up to the required total amount and then chose the combination with the fewest number of coins (top record pattern):
WITH r AS (
SELECT LEVEL-1 n
FROM dual
CONNECT BY LEVEL<=20
), x AS (
SELECT q.n "Quarters", d.n "Dimes", n.n "Nickels", p.n "Pennies",
RANK() OVER(ORDER BY q.n + d.n + n.n + p.n) rk
FROM r q, r d, r n, r p
WHERE q.n<=3
AND d.n<=9
AND n.n<=19 --not needed
AND p.n<=4
AND q.n*25 + d.n*10 + n.n*5 + p.n = 63 --amount of change
)
SELECT "Quarters", "Dimes", "Nickels", "Pennies"
FROM x
WHERE rk=1
If we want to extend this solution to see the change combinations for all values from 1 to 99, we will need to change the above solution as follows:
WITH r AS ( -- this range is to be reused 5 times in this query
SELECT LEVEL-1 n
FROM dual
CONNECT BY LEVEL<=100
), x AS (
SELECT c.n "Change", q.n "Quarters", d.n "Dimes",
n.n "Nickels", p.n "Pennies",
RANK() OVER(PARTITION BY c.n ORDER BY q.n + d.n + n.n + p.n) rk
FROM r q, r d, r n, r p, r c
WHERE q.n<=3
AND d.n<=9
AND n.n<=19 --now it is needed
AND p.n<=4 AND q.n*25 + d.n*10 + n.n*5 + p.n = c.n --amount of change
AND c.n>0
)
SELECT "Change", "Quarters", "Dimes", "Nickels", "Pennies"
FROM x
WHERE rk=1
ORDER BY 1
You can execute the above SQL statements in Oracle Live SQL environment.
My Oracle Group on Facebook:
If you like this post, you may want to join my new Oracle group on Facebook: https://www.facebook.com/groups/sqlpatterns/
Would you like to read about many more tricks and puzzles?
For more tricks and cool techniques check my book “Oracle SQL Tricks and Workarounds” for instructions.
sqlpatterns 