Inverse Coin Change

Start by identifying the smallest denomination where numWays[c] equals 1, then iteratively check multiples and combinations using dynamic programming. Track cumulative possibilities to validate each candidate denomination. Return the sorted set of all valid denominations that match the given numWays array pattern.

Problem Statement

You are given a 1-indexed integer array numWays where numWays[i] represents the number of ways to form the amount i using an infinite supply of some positive coin denominations. The exact denominations have been lost and must be recovered from this array pattern.

Your task is to identify all coin denominations that could have generated the provided numWays array and return them as a sorted array of unique integers. Use state transition dynamic programming to validate each candidate and reconstruct the possible denomination set.

Examples

Example 1

Input: numWays = [0,1,0,2,0,3,0,4,0,5]

Output: [2,4,6]

Input: numWays = [1,2,2,3,4] Output: [1,2,5] Explanation: Example 3: Input: numWays = [1,2,3,4,15] Output: [] Explanation: No set of denomination satisfies this array.

Example 2

Input: numWays = [1,2,2,3,4]

Output: [1,2,5]

Example 3

Input: numWays = [1,2,3,4,15]

Output: []

No set of denomination satisfies this array.

Constraints

• 1 <= numWays.length <= 100
• 0 <= numWays[i] <= 2 * 108

Solution Approach

Identify Minimal Denominations

Scan the numWays array to find the smallest index c where numWays[c] equals 1. This index corresponds to the smallest coin denomination since it must appear in exactly one combination.

Iterative DP Verification

Use dynamic programming to simulate adding candidate denominations. Update a working DP array to reflect the cumulative number of ways to form each amount and confirm consistency with the original numWays array. Reject any denomination that causes mismatch.

Construct Sorted Denomination Set

Once all valid denominations are verified through DP, collect them into a unique set and sort in ascending order. Return this sorted array as the final solution.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time and space complexity depend on the DP verification process, which iteratively checks combinations for each candidate denomination against the numWays array, potentially up to O(n^2) in the worst case for array length n.

What Interviewers Usually Probe

• Look for recognition that numWays[c] == 1 indicates a base denomination.
• Check if candidate denominations are verified via DP rather than guessed.
• Evaluate if solution maintains correctness when multiple valid sets exist.

Common Pitfalls or Variants

Common pitfalls

• Assuming denominations can be any value without checking DP consistency.
• Overlooking that multiples of smaller coins influence subsequent numWays counts.
• Failing to return a sorted unique array, breaking problem constraints.

Follow-up variants

• Recover denominations when numWays array is 0-indexed instead of 1-indexed.
• Determine denominations for numWays arrays allowing limited coin counts per denomination.
• Compute the minimum subset of denominations generating the same numWays pattern.

FAQ

What is the core strategy for solving Inverse Coin Change?

Use state transition dynamic programming to iteratively verify candidate coin denominations against the numWays array.

How do I find the smallest coin denomination?

Locate the first index c where numWays[c] equals 1; this corresponds to the smallest denomination.

Can multiple valid denomination sets exist?

Yes, different combinations may reproduce the same numWays pattern; the algorithm ensures all valid denominations are included.

Why must the final array be sorted and unique?

The problem explicitly requires returning a sorted array of unique denominations to match expected output format.

Does this approach generalize to larger numWays arrays?

Yes, but time and space depend on DP verification; larger arrays may increase computation due to combination checks.