Recover Coins from Change Counts
Google● HardNEW GRADPHONE SCREENONSITE INTERVIEWProblem statement
An unknown set of distinct positive coin denominations was used in the unlimited Coin Change combinations recurrence.
You receive the completed array ways, where ways[a] is the number of order-independent combinations that form amount a. The original recurrence started with ways[0] = 1 and processed every coin in increasing denomination order.
Exactly one valid coin set exists, every denomination is at most ways.length - 1, and every count fits in a signed 64-bit integer. Recover and return the coin denominations in increasing order.
Function
recoverCoins(ways: long[]) → int[]Examples
Example 1
ways = [1,1,1,2,2,3,4]return = [1,3,5]Coins 1, 3, and 5 produce the displayed combination counts through amount 6.
Example 2
ways = [1,0,1,0,1,1]return = [2,5]Amounts 2 and 4 use coin 2, while amount 5 reveals coin 5.
Constraints
2 <= ways.length <= 2000.ways[0] = 1.- Every value is nonnegative and fits in a signed 64-bit integer.
- Exactly one set of distinct positive denominations in
[1, ways.length - 1]produces the array.