# $O(1)$ algorithm for coin change w/out nickels

For the coin changing problem in the case without nickels (only quarters, dimes, and pennies available), assuming you use quarters until $x < 50$ since it's better to use quarters for $x \geq 50$; $x$ is the change) what would be an $O(1)$ algorithm that, given an input $n$, returns the number of quarters, dimes, and pennies that give the correct change with a minimum amount of coins??

## 2 Answers

Depending on your model of computation, you might not even be able to read the input in time $O(1)$. But assuming all the standard arithmetic operations can be done in unit time, which seems to be the case here, the number of quarters (call it $q$) is either $\lfloor n/25 \rfloor$ or $\lfloor n/25 \rfloor + 1$. You then have $n_1 = n - 25 q$ cents to make up with dimes and pennies, and you use $\lfloor n_1/10 \rfloor$ dimes ...

• So continuing the same logic, after using $n_1/10$ dimes I would have $n_2 = n_1 - 10c$. Would the pennies be $n_2/1$ pennies or $n_2 = 1$? – user2645179 Oct 14 '14 at 15:13
• I'm thinking of this correctly? – user2645179 Oct 14 '14 at 17:07
The following is pseudocode that does what you ask:

getCoins(remainder){
if(remainder >= 30){
// 30 <= remainder < 36 || 40 <= remainder < 46
if(remainder % dime < 6){
coins += remainder/dime
coins += remainder % dime
// 36 <= remainder < 39 || 46 <= remainder < 49
} else {//remainder % dime >=6
coins += remainder/quarter
coins += remainder % quarter
}
return coins
// 25 <= remainder < 29
} else if(remainder >= 25){
coins += remainder/quarter
coins += remainder % quarter
return coins
// remainder < 25
} else {
coins += remainder/dime
coins += remainder
return coins
}


}

/* This is the function that, given an amount, will return the minimum number of coins that can change the amount into quarters, dimes and pennies.

change(amount) {
quarter = 25
dime = 10
pennie = 1
coins = 0
/*First we check if the starting amount is greater than 50*/
if(amount >=50){
//If amount=a*50+b, "multiple_of_50" will be a*50 //always.
multiple_of_50 = amount-amount%50
//And here we get b into the variable "remainder"
//for later use
remainder = amount % 50
//Here we add the number of quarters in a*50 to coins.
coins += multiple_of_50/quarter;
/*
Now, because of what we did above, remainder is less than 50 always.
*/
coins += getCoins(remainder)
} else {//amount < 50
coins += getCoins(amount)
}
return coins


}