Problem

You are given an array of length N, where each element i represents the number of ways we can produce i units of change. For example, [1, 0, 1, 1, 2] would indicate that there is only one way to make 0, 2, or 3 units, and two ways of making 4 units.

Given such an array, determine the denominations that must be in use. In the case above, for example, there must be coins with value 2, 3, and 4.

Examples

Example 1

1
2
3
4
5
6
7
8

Input: [1, 0, 1, 1, 2]
Output: [2, 3, 4]
Explanation: 
- Index 0: 1 way to make 0 (using no coins)
- Index 1: 0 ways to make 1 (no coin of value 1)
- Index 2: 1 way to make 2 (using coin of value 2)
- Index 3: 1 way to make 3 (using coin of value 3)
- Index 4: 2 ways to make 4 (using coin of value 4, or using coin of value 2 twice)

Example 2

1
2
3
4
5
6
7
8
9

Input: [1, 1, 1, 1, 1]
Output: [1]
Explanation: 
With coin of value 1, we can make any amount with exactly 1 way:
- 0: use no coins
- 1: use one coin of value 1
- 2: use two coins of value 1
- 3: use three coins of value 1
- 4: use four coins of value 1

Example 3

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Input: [1, 0, 1, 0, 1, 1, 2]
Output: [2, 4, 5]
Explanation:
- 0: 1 way (no coins)
- 1: 0 ways (no coin of value 1)
- 2: 1 way (coin of value 2)
- 3: 0 ways (cannot be made with coins 2, 4, 5)
- 4: 1 way (coin of value 4, or two coins of value 2)
- 5: 1 way (coin of value 5)
- 6: 2 ways (coin 2 + coin 4, or three coins of value 2)

Example 4

1
2
3
4
5
6
7
8
9

Input: [1, 1, 2, 2, 3]
Output: [1, 2]
Explanation:
With coins of value 1 and 2:
- 0: 1 way (no coins)
- 1: 1 way (one coin of value 1)
- 2: 2 ways (one coin of value 2, or two coins of value 1)
- 3: 2 ways (one coin of value 2 + one coin of value 1, or three coins of value 1)
- 4: 3 ways (two coins of value 2, one coin of value 2 + two coins of value 1, or four coins of value 1)

Example 5

1
2
3
4
5
6
7
8

Input: [1, 0, 0, 1]
Output: [3]
Explanation:
Only coin of value 3 exists:
- 0: 1 way (no coins)
- 1: 0 ways (cannot make with coin 3)
- 2: 0 ways (cannot make with coin 3)
- 3: 1 way (one coin of value 3)

Solution

Method 1 - Greedy Denomination Detection

Intuition

We can detect coin denominations by analyzing the change in the number of ways to make different amounts. When we introduce a new coin denomination, it creates additional ways to make certain amounts. If ways[i] > ways[i-d] where d is a potential denomination, then d is likely a valid coin denomination.

Approach

  1. Start with the assumption that we can always make 0 with 1 way (using no coins)
  2. For each position i from 1 to N-1:
    • If ways[i] > 0 and there’s no existing way to make amount i, then i must be a coin denomination
    • Check if introducing coin i would create the observed number of ways
  3. For each potential denomination d, verify it by checking if it contributes correctly to the ways array
  4. Use dynamic programming to validate the denominations by reconstructing the ways array

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

class Solution {
public:
    vector<int> findDenominations(vector<int>& ways) {
        int n = ways.size();
        vector<int> denominations;
        
        // Check each potential denomination
        for (int d = 1; d < n; d++) {
            if (ways[d] > 0) {
                // Check if d could be a valid denomination
                bool isValid = true;
                vector<int> dp(n, 0);
                dp[0] = 1;
                
                // Add current denominations
                for (int coin : denominations) {
                    for (int i = coin; i < n; i++) {
                        dp[i] += dp[i - coin];
                    }
                }
                
                // Add potential denomination d
                for (int i = d; i < n; i++) {
                    dp[i] += dp[i - d];
                }
                
                // Check if adding d makes the dp match ways up to current index
                bool matches = true;
                for (int i = 0; i <= d && i < n; i++) {
                    if (dp[i] != ways[i]) {
                        matches = false;
                        break;
                    }
                }
                
                if (matches) {
                    denominations.push_back(d);
                }
            }
        }
        
        return denominations;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

func findDenominations(ways []int) []int {
    n := len(ways)
    var denominations []int
    
    // Check each potential denomination
    for d := 1; d < n; d++ {
        if ways[d] > 0 {
            // Check if d could be a valid denomination
            dp := make([]int, n)
            dp[0] = 1
            
            // Add current denominations
            for _, coin := range denominations {
                for i := coin; i < n; i++ {
                    dp[i] += dp[i-coin]
                }
            }
            
            // Add potential denomination d
            for i := d; i < n; i++ {
                dp[i] += dp[i-d]
            }
            
            // Check if adding d makes the dp match ways up to current index
            matches := true
            for i := 0; i <= d && i < n; i++ {
                if dp[i] != ways[i] {
                    matches = false
                    break
                }
            }
            
            if matches {
                denominations = append(denominations, d)
            }
        }
    }
    
    return denominations
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

class Solution {
    public List<Integer> findDenominations(int[] ways) {
        int n = ways.length;
        List<Integer> denominations = new ArrayList<>();
        
        // Check each potential denomination
        for (int d = 1; d < n; d++) {
            if (ways[d] > 0) {
                // Check if d could be a valid denomination
                int[] dp = new int[n];
                dp[0] = 1;
                
                // Add current denominations
                for (int coin : denominations) {
                    for (int i = coin; i < n; i++) {
                        dp[i] += dp[i - coin];
                    }
                }
                
                // Add potential denomination d
                for (int i = d; i < n; i++) {
                    dp[i] += dp[i - d];
                }
                
                // Check if adding d makes the dp match ways up to current index
                boolean matches = true;
                for (int i = 0; i <= d && i < n; i++) {
                    if (dp[i] != ways[i]) {
                        matches = false;
                        break;
                    }
                }
                
                if (matches) {
                    denominations.add(d);
                }
            }
        }
        
        return denominations;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution:
    def findDenominations(self, ways: List[int]) -> List[int]:
        n = len(ways)
        denominations = []
        
        # Check each potential denomination
        for d in range(1, n):
            if ways[d] > 0:
                # Check if d could be a valid denomination
                dp = [0] * n
                dp[0] = 1
                
                # Add current denominations
                for coin in denominations:
                    for i in range(coin, n):
                        dp[i] += dp[i - coin]
                
                # Add potential denomination d
                for i in range(d, n):
                    dp[i] += dp[i - d]
                
                # Check if adding d makes the dp match ways up to current index
                matches = True
                for i in range(min(d + 1, n)):
                    if dp[i] != ways[i]:
                        matches = False
                        break
                
                if matches:
                    denominations.append(d)
        
        return denominations

Complexity

  • ⏰ Time complexity: O(N³), where N is the length of the ways array. We check N potential denominations, and for each we do O(N²) work to validate
  • 🧺 Space complexity: O(N), for the dp array used in validation

Method 2 - Optimized Incremental Validation

Intuition

We can optimize by building the solution incrementally. For each position, we check if it could be a new denomination by seeing if it explains the increase in ways compared to what we can already make with existing denominations.

Approach

  1. Initialize dp array where dp[i] represents ways to make amount i with current denominations
  2. Set dp[0] = 1 (one way to make 0)
  3. For each amount i from 1 to N-1:
    • Calculate how many ways we can make i with current denominations
    • If dp[i] < ways[i], then i must be a new denomination
    • Add i to denominations and update dp array accordingly
  4. Return the list of denominations found

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    vector<int> findDenominationsOptimized(vector<int>& ways) {
        int n = ways.size();
        vector<int> denominations;
        vector<int> dp(n, 0);
        dp[0] = 1;
        
        for (int i = 1; i < n; i++) {
            if (dp[i] < ways[i]) {
                // i must be a denomination
                denominations.push_back(i);
                
                // Update dp array with new denomination
                for (int j = i; j < n; j++) {
                    dp[j] += dp[j - i];
                }
            }
        }
        
        return denominations;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func findDenominationsOptimized(ways []int) []int {
    n := len(ways)
    var denominations []int
    dp := make([]int, n)
    dp[0] = 1
    
    for i := 1; i < n; i++ {
        if dp[i] < ways[i] {
            // i must be a denomination
            denominations = append(denominations, i)
            
            // Update dp array with new denomination
            for j := i; j < n; j++ {
                dp[j] += dp[j-i]
            }
        }
    }
    
    return denominations
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public List<Integer> findDenominationsOptimized(int[] ways) {
        int n = ways.length;
        List<Integer> denominations = new ArrayList<>();
        int[] dp = new int[n];
        dp[0] = 1;
        
        for (int i = 1; i < n; i++) {
            if (dp[i] < ways[i]) {
                // i must be a denomination
                denominations.add(i);
                
                // Update dp array with new denomination
                for (int j = i; j < n; j++) {
                    dp[j] += dp[j - i];
                }
            }
        }
        
        return denominations;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def findDenominationsOptimized(self, ways: List[int]) -> List[int]:
        n = len(ways)
        denominations = []
        dp = [0] * n
        dp[0] = 1
        
        for i in range(1, n):
            if dp[i] < ways[i]:
                # i must be a denomination
                denominations.append(i)
                
                # Update dp array with new denomination
                for j in range(i, n):
                    dp[j] += dp[j - i]
        
        return denominations

Complexity

  • ⏰ Time complexity: O(N²), where N is the length of the ways array. For each potential denomination, we update the dp array in O(N) time
  • 🧺 Space complexity: O(N), for the dp array to track ways to make each amount