Inverse Coin Change
You are given a 1-indexed integer array numWays, where numWays[i] represents the number of ways to select a total amount i using an infinite supply of some fixed coin denominations.
You are given a 1-indexed integer array numWays, where numWays[i] represents the number of ways to select a total amount i using an infinite supply of some fixed coin denominations. Each denomination is a positive integer with value at most numWays.length.
However, the exact coin denominations have been lost. Your task is to recover the set of denominations that could have resulted in the given numWays array.
Return a sorted array containing unique integers which represents this set of denominations.
If no such set exists, return an empty array.
Example 1
Input: numWays = [1,2,3,4,15]
Output: []
Explanation: Example 3: 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: []
Explanation: No set of denomination satisfies this array.
Constraints
- 1 <= numWays.length <= 100
- 0 <= numWays[i] <= 2 * 10^8
Hints
Companies
No companies reported yet.
Discussion
Sign in to join the discussion.
Loading discussion...
Test results
No test cases yet.