1
$\begingroup$

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??

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – user2645179 Oct 14 '14 at 15:13
  • $\begingroup$ I'm thinking of this correctly? $\endgroup$ – user2645179 Oct 14 '14 at 17:07
0
$\begingroup$
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

}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.