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

Why are you creating a huge array, let alone whose size is depending on user input, when you only need number of coins as output? — Aqeel Ashiq, Nov 14 '22 at 15:47
@SyedAqeelAshiq, I am using the code from the reference link I added in my post. — learner, Nov 14 '22 at 15:49
Consider something for a moment: `50` is just 5 `10` coins, and `30` is just 3 `10` coins. In essence, you can always model it if it's a multiple of `10` (the largest number `M` possible). The smallest number `M` would have a total of `sum/50` coins of size `50`, and at most 2 other coins `30+10`, `30`, `10+10`, or `10`. From there, it's a matter of swapping out the `50`/`30` coins for `10` coins if you need to increase `M`. — Rogue, Nov 14 '22 at 15:57
@Rogue. I want to select all possible ways to get the sum and also I want to select exactly M coins for each case to get that sum. — learner, Nov 14 '22 at 15:59
Are you asking for a general solution, or one that just works for coins of value 10, 30, 50? — Paul Hankin, Nov 14 '22 at 15:59
@PaulHankin, I want to use only the coins 10, 30 and 50. Not a general solution. — learner, Nov 14 '22 at 16:00
https://stackoverflow.com/a/71359069/585411 shows how to solve this. But you have to first change the set of coins to a set of `m` copies of each coin, then look for `m` of them. — btilly, Nov 14 '22 at 17:28
Side note: `new long[sum+1];` automatically initializes all array elements to `0`. `Arrays.fill()` is redundant. — Janez Kuhar, Nov 16 '22 at 20:07
@learner If you only want specific solution for just 3 denominations, then why just place 3 nested loops. Iterations can be drastically reduced by applying different conditions like sum or Number of coins exceeding the required limits. Are there other memory or CPU requirements which are overrun by nested loops? — Aqeel Ashiq, Nov 17 '22 at 08:32

Idle_Mind · Answer 1 · 2022-11-14T20:11:20.173

One way to think about this problem is to count in a different base system. You use the number of unique coins as the base. So for your example of 10, 30, and 50, the base would be 3.

Now you need numbers in that base system that have the correct number of digits, which is 4 for your example. Since each digit can be only one of 3 values in base 3 (0, 1, or 2), the total number of possibilites is 3 raised to the power of 4, or 81.

Thus we can count from 0 to 80 in decimal, and convert that decimal number to a four digit base 3 number using stacked repeated division.

Here's what those four digit base 3 numbers would look like:

0 in base 3: [0, 0, 0, 0]
1 in base 3: [0, 0, 0, 1]
2 in base 3: [0, 0, 0, 2]
3 in base 3: [0, 0, 1, 0]
4 in base 3: [0, 0, 1, 1]
5 in base 3: [0, 0, 1, 2]
6 in base 3: [0, 0, 2, 0]
7 in base 3: [0, 0, 2, 1]
8 in base 3: [0, 0, 2, 2]
9 in base 3: [0, 1, 0, 0]
10 in base 3: [0, 1, 0, 1]
11 in base 3: [0, 1, 0, 2]
12 in base 3: [0, 1, 1, 0]
13 in base 3: [0, 1, 1, 1]
14 in base 3: [0, 1, 1, 2]
15 in base 3: [0, 1, 2, 0]
16 in base 3: [0, 1, 2, 1]
17 in base 3: [0, 1, 2, 2]
18 in base 3: [0, 2, 0, 0]
19 in base 3: [0, 2, 0, 1]
20 in base 3: [0, 2, 0, 2]
21 in base 3: [0, 2, 1, 0]
22 in base 3: [0, 2, 1, 1]
23 in base 3: [0, 2, 1, 2]
24 in base 3: [0, 2, 2, 0]
25 in base 3: [0, 2, 2, 1]
26 in base 3: [0, 2, 2, 2]
27 in base 3: [1, 0, 0, 0]
28 in base 3: [1, 0, 0, 1]
29 in base 3: [1, 0, 0, 2]
30 in base 3: [1, 0, 1, 0]
31 in base 3: [1, 0, 1, 1]
32 in base 3: [1, 0, 1, 2]
33 in base 3: [1, 0, 2, 0]
34 in base 3: [1, 0, 2, 1]
35 in base 3: [1, 0, 2, 2]
36 in base 3: [1, 1, 0, 0]
37 in base 3: [1, 1, 0, 1]
38 in base 3: [1, 1, 0, 2]
39 in base 3: [1, 1, 1, 0]
40 in base 3: [1, 1, 1, 1]
41 in base 3: [1, 1, 1, 2]
42 in base 3: [1, 1, 2, 0]
43 in base 3: [1, 1, 2, 1]
44 in base 3: [1, 1, 2, 2]
45 in base 3: [1, 2, 0, 0]
46 in base 3: [1, 2, 0, 1]
47 in base 3: [1, 2, 0, 2]
48 in base 3: [1, 2, 1, 0]
49 in base 3: [1, 2, 1, 1]
50 in base 3: [1, 2, 1, 2]
51 in base 3: [1, 2, 2, 0]
52 in base 3: [1, 2, 2, 1]
53 in base 3: [1, 2, 2, 2]
54 in base 3: [2, 0, 0, 0]
55 in base 3: [2, 0, 0, 1]
56 in base 3: [2, 0, 0, 2]
57 in base 3: [2, 0, 1, 0]
58 in base 3: [2, 0, 1, 1]
59 in base 3: [2, 0, 1, 2]
60 in base 3: [2, 0, 2, 0]
61 in base 3: [2, 0, 2, 1]
62 in base 3: [2, 0, 2, 2]
63 in base 3: [2, 1, 0, 0]
64 in base 3: [2, 1, 0, 1]
65 in base 3: [2, 1, 0, 2]
66 in base 3: [2, 1, 1, 0]
67 in base 3: [2, 1, 1, 1]
68 in base 3: [2, 1, 1, 2]
69 in base 3: [2, 1, 2, 0]
70 in base 3: [2, 1, 2, 1]
71 in base 3: [2, 1, 2, 2]
72 in base 3: [2, 2, 0, 0]
73 in base 3: [2, 2, 0, 1]
74 in base 3: [2, 2, 0, 2]
75 in base 3: [2, 2, 1, 0]
76 in base 3: [2, 2, 1, 1]
77 in base 3: [2, 2, 1, 2]
78 in base 3: [2, 2, 2, 0]
79 in base 3: [2, 2, 2, 1]
80 in base 3: [2, 2, 2, 2]

The integer in each resulting array (the base 3 number) represents which coin from the original coin values should go in that spot (0 = 10, 1 = 30, 2 = 50).

For example, the number 61 in decimal is 2021 in base 3:

61 in base 3: [2, 0, 2, 1]

The resulting coin combination for that number would be:

50, 10, 50, 30

Here's the code that generated the list of base 3 numbers above:

import java.util.Arrays;
class Main {
  
  public static void main(String[] args) {
    int sum = 80;
    int numCoins = 4;
    int[] coins = new int[]{10, 30, 50};
    
    int base = coins.length;    
    int combos = (int)Math.pow(base, numCoins); 

    int[][] combinations = new int[combos][];
    for(int d=0; d<combos; d++) {
      combinations[d] = convertToBase(d, base, numCoins);
      System.out.println(d + " in base " + base + ": " + Arrays.toString(combinations[d]));
    }
  }

  public static int[] convertToBase(int decimalNumber, int base, int numDigits) {    
    int[] digits = new int[numDigits];
    int index = digits.length - 1;

    int quotient = decimalNumber;
    while (quotient > 0) {
      digits[index] = quotient % base;
      index--;
      quotient = quotient / base;
    }
    
    return digits;
  }
  
}

Now that you have all possible combinations of four coins, you need to add up the values from each combo and see if they add up to 80.

Here's a new main() to do just that:

  public static void main(String[] args) {
    int sum = 80;
    int numCoins = 4;
    int[] coins = new int[]{10, 30, 50};
    
    int base = coins.length;    
    int combos = (int)Math.pow(base, numCoins); 

    int[][] combinations = new int[combos][];
    for(int d=0; d<combos; d++) {
      combinations[d] = convertToBase(d, base, numCoins);

      String combo = "";
      int curSum = 0;
      for(int coinChoice : combinations[d]) {
        combo = combo + coins[coinChoice] + " ";
        curSum = curSum + coins[coinChoice];
      }
      
      if (curSum == sum) {
        System.out.println("Coins: " + combo + " = " + curSum);
      }
    }
  }

Producing the following output:

Coins: 10 10 10 50  = 80
Coins: 10 10 30 30  = 80
Coins: 10 10 50 10  = 80
Coins: 10 30 10 30  = 80
Coins: 10 30 30 10  = 80
Coins: 10 50 10 10  = 80
Coins: 30 10 10 30  = 80
Coins: 30 10 30 10  = 80
Coins: 30 30 10 10  = 80
Coins: 50 10 10 10  = 80

Notice that there are repeats because the same combination of coin denominations could be put into different positions of the four slots.

If you want to get rid of duplicates, you could SORT the resulting combos and add them to a Hashmap if they don't already exist (add import java.util.HashMap;):

  public static void main(String[] args) {
    int sum = 80;
    int numCoins = 4;
    int[] coins = new int[]{10, 30, 50};
    
    int base = coins.length;    
    int combos = (int)Math.pow(base, numCoins); 

    int[][] combinations = new int[combos][];
    HashMap<String, String> uniqueCombos = new HashMap<String, String>();
    for(int d=0; d<combos; d++) {
      combinations[d] = convertToBase(d, base, numCoins);

      String combo = "";
      int curSum = 0;
      for(int coinChoice : combinations[d]) {
        combo = combo + coins[coinChoice] + " ";
        curSum = curSum + coins[coinChoice];
      }
      
      if (curSum == sum) {
        Arrays.sort(combinations[d]);
        String key = Arrays.toString(combinations[d]);
        if (!uniqueCombos.containsKey(key)) {
          uniqueCombos.put(key, combo);
          System.out.println("Coins: " + combo + " = " + curSum);
        }  
      }
    }
  }

Now we only get the two unique combinations in our output:

Coins: 10 10 10 50  = 80
Coins: 10 10 30 30  = 80

Here is the final version of the entire program:

import java.util.Arrays;
import java.util.HashMap;
class Main {
  
  public static void main(String[] args) {
    int sum = 80;
    int numCoins = 4;
    int[] coins = new int[]{10, 30, 50};
    
    int base = coins.length;    
    int combos = (int)Math.pow(base, numCoins); 

    int[][] combinations = new int[combos][];
    HashMap<String, String> uniqueCombos = new HashMap<String, String>();
    for(int d=0; d<combos; d++) {
      combinations[d] = convertToBase(d, base, numCoins);

      String combo = "";
      int curSum = 0;
      for(int coinChoice : combinations[d]) {
        combo = combo + coins[coinChoice] + " ";
        curSum = curSum + coins[coinChoice];
      }
      
      if (curSum == sum) {
        Arrays.sort(combinations[d]);
        String key = Arrays.toString(combinations[d]);
        if (!uniqueCombos.containsKey(key)) {
          uniqueCombos.put(key, combo);
          System.out.println("Coins: " + combo + " = " + curSum);
        }  
      }
    }
  }

  public static int[] convertToBase(int decimalNumber, int base, int numDigits) {    
    int[] digits = new int[numDigits];
    int index = digits.length - 1;

    int quotient = decimalNumber;
    while (quotient > 0) {
      digits[index] = quotient % base;
      index--;
      quotient = quotient / base;
    }
    
    return digits;
  }
  
}

I am getting OutOfMemory Errors because of line `int[][] combinations = new int[combos][];` — learner, Nov 15 '22 at 15:16
We can completely get rid of that array and the algorithm will be the same (by storing the smaller returned digits array directly in a local varaible)...but 3^5000 is a really BIG number; my approach won't work for inputs that high. Sorry. Good luck with that! — Idle_Mind, Nov 15 '22 at 15:43
It is possible to count in another base using a different approach, manipulating the digits directly in an array (or with a String) , thus not requiring integer division or modulus on large numbers. You'd follow the literal counting algorithm as described in my first link. Would you like to see that approach instead? *The run time is still going to be INCREDIBLY LONG for 5,000 digits! — Idle_Mind, Nov 15 '22 at 16:19
Thank you very much for providing an idea for this. I am fine with this answer — learner, Nov 15 '22 at 17:05
Well with logic that deep and totally different direction, I thought it would be O(n) in memory and CPU. But in the end it turned out O(n^n^n^God knows what else) for both CPU and memory. Strange it got accepted as correct answer. -1. And +1 for the effor though — Aqeel Ashiq, Nov 16 '22 at 05:15

score 2 · Accepted Answer · edited Nov 16 '22 at 19:17

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

Alexander Ivanchenko · Answer 3 · 2022-11-15T02:31:56.387

// 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]];

The overall direction is correct, Dynamic Programming is the right tool for this problem.

But there's a couple of serious mistakes in your solution:

The outer for-loop should iterate over the coins, but in the snippet above, the outer loop iterates over the amounts (index i represents a particular amount). As a consequence, as the end result you'll get not a number of distinct Combinations, but a number of Permutations because in the approach you've taken two identical sets of coins arranged differently would be taken into account. For example, based on the logic of the code permutations like 10 + 10 + 50 + 10 and 10 + 10 + 10 + 50 would contribute the amount of 80, which not correct according to the problem description.
The second issue is much easier to spot, but nevertheless it's important: you're not checking if the array index to which you're referring to exists, which would lead to an ArrayIndexOutOfBoundsException.

So, the main takeaway - we number the number of Combinations, and for that we need to consider each coin separately from other coins, i.e. the outer loop should perform iteration over the given array of coins.

To make the solution more comprehensible, I'll represent each combination of coins and each group of coin-combinations having the same total amount as objects Combination and Combinations respectively.

The array that would accumulate the result would be of type Combinations[]. Each Combination has two properties: limit and coinCount representing the required and current number of coins respectively. Combinations which coinCount exceeds the limit would be discarded on the fly, the rest would filtered out while producing the resulting value.

public static long countWays(int[] coins, int n, int sum) {
    
    Combinations[] table = new Combinations[sum + 1];
    
    table[0] = Combinations.withOneNoCoinsComb(n);
    
    for (int coin : coins) {
        
        for (int i = 0; i < table.length; i++) {
            // no combinations representing this amount or i + coin exceeds the sum
            if (table[i] == null || i + coin > sum) continue;
            
            if (table[i + coin] == null) {
                table[i + coin] = Combinations.getEmpty(); // creating an empty Combinations instance
            }
            
            table[i + coin].addCombinations(table[i]); // adding the combinations from the previous array position representing amount i
        }
    }
    return table[sum].getValidCombCount();
}

Custom classes Combinations and Combination:

public class Combinations {
    private List<Combination> comb = new ArrayList<>();
    
    private Combinations() {}
    
    public void addCombinations(Combinations other) {
        for (Combination c : other.comb) {
            if (c.canAdd()) this.comb.add(Combination.copyOf(c).addCoin());
        }
    }
    
    public int getValidCombCount() {
        return (int) comb.stream().filter(Combination::isValid).count();
    }
    
    private static Combinations withOneNoCoinsComb(int limit) {
        Combinations oneComb = new Combinations();
        oneComb.addCombination(new Combination(limit));
        return oneComb;
    }
    
    private static Combinations getEmpty() {
        return new Combinations();
    }
    
    public void addCombination(Combination c) {
        comb.add(c);
    }
    
    // getters
}

public class Combination {
    private final int limit; // m - max number of coins
    private int coinCount;
    
    public Combination(int limit) {
        this.limit = limit;
    }
    
    public Combination(int limit, int coinCount) {
        this.limit = limit;
        this.coinCount = coinCount;
    }
    
    public Combination addCoin() {
        coinCount++;
        return this;
    }
    
    public boolean canAdd() {
        return coinCount <= limit;
    }
    
    public boolean isValid() {
        return coinCount == limit;
    }
    
    public static Combination copyOf(Combination c) {
        return new Combination(c.getLimit(), c.getCoinCount());
    }
    
    // getters
}

main()

public static void main(String[] args) {
    System.out.println(countWays(new int[]{10, 30, 50}, 4, 80));
}

Output:

I am getting OutOfMemory Errors becase of method addCombinations while adding element to ArrayList when input has values (5000, 190000) — learner, Nov 15 '22 at 15:17
@learner At least I've explained how to apply Tabulation approach to this problem correctly and gave a viable implementation. Since you're dialing with such massive numbers, this task requires a different algorithm, and I can't provide another solution immediately. — Alexander Ivanchenko, Nov 15 '22 at 15:43

Coin change problem with a condition to use exactly m coints

3 Answers3