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));

}

All Permutations of String

Question: Generate all permutations of a given string.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

private List<String> permutations = new ArrayList<String>();           /**      *  Generate all the  permutations and add to array list      *       * @param in      * @param out      * @param used      * @param len      * @param recLen      */     void permute(char[] in, char[] out, char[] used, int len, int recLen)     {               if(recLen==len) {             permutations.add(String.valueOf(out));              return;         }               for(int i=0; i<len; i++) {             if(used[i]==1) {                 continue;             }             out[recLen]=in[i];             used[i]=1;             permute(in, out, used, len, recLen+1);             used[i]=0;         }           }           List<String> permutations(String num)     {         char[] out = new char[num.length()];         char[] used = new char[num.length()];               permute(num.toCharArray(), out, used, num.length(), 0);         return permutations;     }