1.

Write a program to calculate how many ways can we make change for N cents if we have an endless supply of each of the C = C1, C2,..Cm valued coins? It makes no difference what order the coins are placed in.

Answer»

Example:
Input :
N = 4, C = { 1, 2, 3}
Output : 
4
Explanation:
There are 4 possible combinations : {1, 1, 1, 1}, {1, 1, 2}, {1, 3}, {2, 2}

Input :
N = 10, C = {2, 3, 5, 6}
Output :
5
Explanation:
There are 5 possible combinations ; {2, 2, 2, 2, 2}, {2, 2, 3, 3}, {2, 2, 6}, {2, 3, 5}, {5, 5}

Approach:

We can divide all set solutions into TWO sets to count the total number of solutions.

1) Solutions that are devoid of the mth COIN (or Cm).

2) At least one Cm is present in the solution.

If solve(C[], m, n) is the function for counting the number of solutions, it may be represented as the sum of solve(C[], m-1, n) and solve(C[], m, n-Cm). We will use dynamic PROGRAMMING to store the result for a particular VALUE of n and m. This will optimise our time complexity to O(nm).

Code:

 #include<bits/stdc++.h>using namespace std;// function to count the number of ways n can be represented from a coin set of SIZE mint solve( int C[], int m, int n ){ int dp[n + 1][m];//Creating a 2D matrix of size (n + 1) 8 m to store the result of each state of our problem // Filling the matrix for the base case when n = 0 for (int i = 0; i < m; i++) dp[0][i] = 1; // Filling the entries in the dp table in bottom up fashion for (int i = 1; i < n + 1; i++) { for (int j = 0; j < m; j++) { // Including C[j] in our current state's answer int x = (i-C[j] >= 0) ? dp[i - C[j]][j] : 0; // Excluding C[j] in our current state's answer int y = (j >= 1) ? dp[i][j - 1] : 0; // storing the sum of x and y in our current state's answer dp[i][j] = x + y; } } return dp[n][m - 1];} int main(){ int C[] = {2, 3, 5, 6}; int m = sizeof(C)/sizeof(C[0]); int n = 10; cout << solve(C, m, n); return 0;}

Output:

 5

Explanation:

In the above code, we define a function named ‘solve’ which returns the number of ways in which n can be represented from a set of m coins having distinct values. We create a dp table of size (n+1) * m. dp[i][j] represents the number of ways in which i can be represented by a set of j coins. Here, we have used the recurrence formula dp[i][j] = x + y. Here, x = dp[i - C[j]][j], y = dp[i][j-1].


Discussion

No Comment Found

Related InterviewSolutions