Is Inverse Coin Change easy or hard?

Inverse Coin Change is typically rated Medium. The forward coin change DP is standard, but recognizing how to reconstruct the coin set from the DP table requires deeper understanding of dynamic programming transitions.

Inverse Coin Change Python/Java solution

Most implementations follow the same structure: initialize a DP array with dp[0] = 1, iterate through the ways array, detect missing contributions, add the corresponding coin, and update dp using the classic coin change transition. The logic translates directly across Python, Java, C++, and Go.

How to solve Inverse Coin Change in O(n^2)?

Initialize dp[0] = 1 and iterate amounts from 1 to n. If the current dp[i] does not match the provided ways[i], add coin i to the set and update all states j ≥ i using dp[j] += dp[j - i]. Continue until the generated DP array matches the given array.

What is the best approach for Inverse Coin Change?

Dynamic programming reconstruction is the most efficient approach. Build a DP array the same way the classic coin change algorithm works and compare it with the provided ways array. Whenever the computed value is smaller than the expected value at index i, introduce a coin of value i and update the DP table. This runs in O(n^2) time and O(n) space.

Is Inverse Coin Change asked at Google/Amazon/Meta?

Variants of reverse dynamic programming and coin change reconstruction appear in interviews at companies like Google, Amazon, and Meta. Interviewers often test whether candidates understand how DP states are formed and whether they can reason about reversing the transition process.

What data structure is used in Inverse Coin Change?

The core data structure is a one‑dimensional dynamic programming array that stores the number of ways to form each amount. The algorithm also maintains a list or array of discovered coin denominations during reconstruction.

What is the time complexity of Inverse Coin Change?

The optimal reconstruction approach runs in O(n^2) time because every discovered coin may update the DP array from its value up to n. The algorithm uses O(n) additional space for the DP table used during reconstruction.

Description Hints 5 Video 13:17

3592. Inverse Coin Change

Medium52.2% acceptance2 companies

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 = [0,1,0,2,0,3,0,4,0,5]

Output: [2,4,6]

Explanation:

Amount	Number of ways	Explanation
1	0	There is no way to select coins with total value 1.
2	1	The only way is `[2]`.
3	0	There is no way to select coins with total value 3.
4	2	The ways are `[2, 2]` and `[4]`.
5	0	There is no way to select coins with total value 5.
6	3	The ways are `[2, 2, 2]`, `[2, 4]`, and `[6]`.
7	0	There is no way to select coins with total value 7.
8	4	The ways are `[2, 2, 2, 2]`, `[2, 2, 4]`, `[2, 6]`, and `[4, 4]`.
9	0	There is no way to select coins with total value 9.
10	5	The ways are `[2, 2, 2, 2, 2]`, `[2, 2, 2, 4]`, `[2, 4, 4]`, `[2, 2, 6]`, and `[4, 6]`.

Example 2:

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

Output: [1,2,5]

Explanation:

Amount	Number of ways	Explanation
1	1	The only way is `[1]`.
2	2	The ways are `[1, 1]` and `[2]`.
3	2	The ways are `[1, 1, 1]` and `[1, 2]`.
4	3	The ways are `[1, 1, 1, 1]`, `[1, 1, 2]`, and `[2, 2]`.
5	4	The ways are `[1, 1, 1, 1, 1]`, `[1, 1, 1, 2]`, `[1, 2, 2]`, and `[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⁸

Asked at 2 companies

Google Meta

Topics

Array Dynamic Programming

Hints open one at a time

Hint 1

Observe that for the smallest denomination c, you must have numWays[c] == 1.

Hint 2

Find the smallest c > 0 with numWays[c] == 1 and append c to your ans list.

Hint 3

"Remove" that coin’s contribution by doing, for each s from c up to n: numWays[s] -= numWays[s - c]

Hint 4

Repeat: pick the next smallest c with numWays[c] == 1, remove it, and so on.

Hint 5

At the end, if numWays is all zeros, your ans is valid; otherwise, return an empty array.

3592. Inverse Coin Change

Asked at 2 companies

Topics

Hints open one at a time

Similar problems