Interview Questions

Coin Change - Provide denominations

Problem Statement:

How many different ways can you make change for an amount, given a list of coins? In this problem, your code will need to efficiently compute the answer.

Task

Write a program that, given

    The amount N to make change for and the number of types M of infinitely available coins
    A list of M coins - C={C1,C2,C3,..,CM}C={C1,C2,C3,..,CM}

Prints out how many different ways you can make change from the coins to STDOUT.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

public static long[][] diffCount = null;

    public static void main(String args[] ) throws Exception {
       
                Scanner in = new Scanner(System.in);
                         int n = in.nextInt();
                         int p = in.nextInt();
                     
                        int[] input = new int[p];
                         
                         for(int i=0;i<p;i++)
                         {
                                input[i] = in.nextInt();
                         }
                     
                Arrays.sort(input);
                System.out.println(ways(n,input));
                    }

        public static long ways(int n, int[] input) {

                int[][] store = new int[n / input[0]][input.length];

                diffCount = new long[input.length + 1][250 + 1];

                long count = 0;

                // intermediate sum calculation
                for (int i = 0; i < input.length; i++) {
                        for (int j = 0; j < store.length; j++) {
                                if (j == 0) {
                                        store[j][i] = store[j][i] + input[i];

                                } else {
                                        if (store[j - 1][i] + input[i] <= n) {
                                                store[j][i] = store[j - 1][i] + input[i];

                                        } else
                                                break;
                                }
                        }
                }

                count = getDiffPartCount(store, n, 0, 0);

                return count;
        }

        public static long getDiffPartCount(int[][] store, int diff, int row, int index) {
               
                long count = 0;

                for (int i = index; i < store[0].length; i++) {

                        if (store[0][i] > diff)
                                continue;

                        for (int j = 0; j < store.length && store[j][i] <= diff
                                        && store[j][i] > 0; j++) {
                                if (diff == store[j][i]) {

                                        count++;
                                        break;
                                } else if (diff > store[j][i] && store[j][i] > 0) {

                                        int act = diff - store[j][i];
                                        long cnt = 0;
                                        if (i + 1 < store[0].length && act > 0) {
                                                if (diffCount[i + 1][act] == 0) {
                                                        cnt = getDiffPartCount(store, act, j, i + 1);
                                                        if (cnt == 0)
                                                                diffCount[i + 1][act] = -99;
                                                        else
                                                                diffCount[i + 1][act] = diffCount[i + 1][act]
                                                                                + cnt;
                                                } else if (diffCount[i + 1][act] == -99) {
                                                        cnt = 0;
                                                } else {
                                                        cnt = diffCount[i + 1][act];
                                                }
                                                if (cnt >= 1)
                                                        count = count + cnt;

                                                continue;
                                        } else {

                                                continue;
                                        }
                                } else {
                                        break;
                                }
                        }
                }

                return count;
        }
               
                       
                 
}