Find Coin Denominations from Change Count
MediumUpdated: Aug 10, 2025
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
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
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
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
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
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
- Start with the assumption that we can always make 0 with 1 way (using no coins)
- 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
- For each potential denomination d, verify it by checking if it contributes correctly to the ways array
- Use dynamic programming to validate the denominations by reconstructing the ways array
Code
C++
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;
}
};
Go
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
}
Java
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;
}
}
Python
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
- Initialize dp array where dp[i] represents ways to make amount i with current denominations
- Set dp[0] = 1 (one way to make 0)
- 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
- Return the list of denominations found
Code
C++
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;
}
};
Go
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
}
Java
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;
}
}
Python
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