Coin change problem with a condition to use exactly m coints

Question

I have coins for 10, 30 and 50. But I want to use only M coins to get a given sum.

I have this code (from this as reference) that just find all possible ways to get the total sum without applying the condition of using only M coins.

static long countWays(int coins[], int n, int sum)
    {
        // Time complexity of this function: O(n*sum)
        // Space Complexity of this function: O(sum)
 
        // table[i] will be storing the number of solutions
        // for value i. We need sum+1 rows as the table is
        // constructed in bottom up manner using the base
        // case (sum = 0)
        long[] table = new long[sum + 1];
 
        // Initialize all table values as 0
        Arrays.fill(table, 0);
 
        // Base case (If given value is 0)
        table[0] = 1;
 
        // Pick all coins one by one and update the table[]
        // values after the index greater than or equal to
        // the value of the picked coin
        for (int i = 0; i < n; i++)
            for (int j = coins[i]; j <= sum; j++)
                table[j] += table[j - coins[i]];
 
        return table[sum];
    }
 
    // Driver Function to test above function
    public static void main(String args[])
    {
        int coins[] = { 10, 30, 50 };
        int n = coins.length;
        int sum = 80;
        System.out.println(countWays(coins, n, sum));
    }

How can we add that condition for this problem or is there any alternate approach for this.

For example:

M=4 and sum = 80

Output 2.

Explanation:

case 1 : 10*2 + 30*2 = 80 ( used 4 coins i.e. M coins)
case 2 : 10*3 + 50*1 = 80 ( used 4 coins i.e. M coins)

Constraints:

M reaches up to 5000
sum reaches up to 250000

Answer 1

You want to find all i>=0, j>=0, k>=0 such that:

 10i + 30j + 50k = S
   i +   j +   k = M

For any particular k, there's at most one solution for i and j. Solving:

10i + 30j = S - 50k
  i +   j = M - k

gives:

j = M - i - k

10i + 30j = S - 50k
10i + 30(M - i - k) = S - 50k
10i + 30M - 30i - 30k = S - 50k
-20i = S - 50k - 30M + 30k
-20i = S - 20k - 30M
20i = -S + 20k + 30M
i = (30M + 20k - S) / 20

Now, i is an integer if 30M+20k-S is divisible by 20, which is when 30M-S is divisible by 20. If i is an integer, then j is also an integer.

Now we just need to find the range of k for which i and j are both non-negative.

Well, i>=0 when 30M+20k-S>=0, ie. when 20k >= S-30M, or k >= (S-30M)/20.

And j>=0, when M-i-k>=0, ie. when M-(30M+20k-S)/20 - k >= 0, or 20M-30M-20k+S - 20k >= 0, or 40k <= S-10M, or k <= (S-10M)/40.

So without writing a program, we can solve this problem: if 30M-S is not divisible by 20, then there's no solutions. Otherwise, we find the upper and lower bounds for k so that i and j are non-negative.

For example, when M=4 and sum=80, 30M-S=40 which is divisible by 20, we have i>=0 when k>=(S-30M)/20=(80-120)/20=-2 and j>=0 when k<=(S-10M)/40=(80-40)/40=1. We also need 0<=k<=M, so k=0 and k=1 are the two solutions.

An example program (in Python, but easy to convert to whatever you like):

def ways(M, S):
    if (30*M-S) % 20 != 0:
        return 0
    top = min(M, (S-10*M)//40)
    bot = max(0, (S-30*M)//20)
    if top < bot:
        return 0
    return top - bot + 1