Coin Change

Given an in nite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent), write code to calculate the number of ways of representing n cents.

Sol 1:

public int coinChnage(int[] a, int n, int k) {

// there are no coins OR k is less than 0, then no solution exist

if (n <= 0 || k < 0) {

return 0;

}

// If k is 0 then there is 1 solution

if (k == 0) {

return 1;

}

return coinChnage(a, n - 1, k) + coinChnage(a, n, k - a[n - 1]);

}

Sol 2:

 public int makeChange(int n, int denom) {

int next_denom = 0;

switch (denom) {

case 25:

next_denom = 10;

break;

case 10:

next_denom = 5;

break;

case 5:

next_denom = 1;

break;

case 1:

return 1;

}

int ways = 0;

for (int i = 0; i * denom <= n; i++) {

ways += makeChange(n - i * denom, next_denom);

}

return ways;

}

public static void main(String[] args) {

// TODO Auto-generated method stub

CoinChange c = new CoinChange();

int[] a = {25, 10, 5, 1};

System.out.println(c.coinChnage(a, 4, 100));

System.out.println(c.makeChange(100, 25));

}