Paytm Question: Coin change problem

Problem: Find the number of ways of making changes for a given amount of Rupees/Cents etc.

Solution: Following are the steps to achieve the desired result -

1. Construct a table of size value + 1 where table[i] will tell the number of changes available using given coins.
2. Base case is 0 where table[0] = 1 as there is only one way to get the change of 0 i.e. leaving all coins.
3. Fill the table in bottom up manner by picking all coins one by one and update the table[j] where coins[i] <= j <= value.
4. table[n] contains the desired result.

Implementation:

int countChange(int coins[], int numOfCoins, int value)

{

int *table = new int[value + 1];

table[0] = 1;

for(int i = 1; i <= value; ++i)

table[i] = 0;

for(int i = 0; i < numOfCoins; ++i)

{

for(int j = coins[i]; j <= value; ++j)

table[j] += table[j - coins[i]];

}

return table[value];

}

Complexity: O(mn)