# 2018 Puzzle of the Week #3:

# 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

# Solutions:

## 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 dualCONNECT BY LEVEL<=99) SELECT cents "Change", Q "Quarters", D "Dimes", N "Nickels", P "Pennies" FROM m MODELPARTITION 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 ( SELECTLEVEL-1n FROM dual CONNECT BYLEVEL<=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 querySELECT LEVEL-1 n FROM dual CONNECT BY LEVEL<=100), x AS ( SELECTc.n "Change", q.n "Quarters", d.n "Dimes", n.n "Nickels", p.n "Pennies", RANK() OVER(PARTITION BY c.nORDER BY q.n + d.n + n.n + p.n) rk FROM r q, r d, r n, r p,r cWHERE q.n<=3 AND d.n<=9 AND n.n<=19--now it is neededAND p.n<=4 AND q.n*25 + d.n*10 + n.n*5 + p.n = c.n --amount of changeAND 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.