Tuesday 10 September 2013

Combinations of coins


Write a function that takes an integer number and return the count of unique combinations of coins.
(Note : coins = {1, 2, 5, 10})
Example
Input : 3
Output : 2 (because we can make 3 by 1+1+1 or 1+2)

Input : 5
Output : 4 (because we can make 5 by 1+1+1+1+1, 1+1+1+2, 1+2+2, 5)

Implementation

class MakeChange{
static int makeChange2(int n, int denom){
//Base condition
if(n == 0)
return 1;

if(n < 0 || denom == 0)
return 0;

int nextDenom = getNextDenom(denom); //get the next denominator
//either take the current denominator or eliminate it
return makeChange2(n - denom, denom) + makeChange2(n, nextDenom);
}

//Utility function to get the next denominator
static int getNextDenom(int denom){
if(denom == 1)
return 2;
else if(denom == 2)
return 5;
else if(denom == 5)
return 10;
else
return 0;
}

public static void main(String... args){
int n = 5;
int change = makeChange2(n, 1);
System.out.println(change);
}
}

No comments:

Post a Comment