# 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.