Inverse Coin Change

Inverse Coin Change

1. What is this problem about?

The Inverse Coin Change interview question is a creative twist on the classic coin change problem. Instead of finding the minimum coins to make a sum, you are given the results of a "minimum coins" function for various sums, and you need to reconstruct the original set of coin denominations.

2. Why is this asked in interviews?

Google uses the Inverse Coin Change coding problem to evaluate a candidate's ability to "reverse-engineer" an algorithm. It tests your understanding of Dynamic Programming foundations—specifically how state transitions build up. It’s a high-level test of logical deduction and mathematical modeling.

3. Algorithmic pattern used

This problem relies on Greedy deduction within DP states.

1. The Core Rule: In a standard coin change DP, dp[i] = 1 + min(dp[i - coin]).
2. The Reversal: If dp[i] == 1, then i itself must be a coin denomination.
3. Algorithm:
   • Iterate through sums $i = 1, 2, \dots$
   • If the provided result for sum $i$ is 1, add $i$ to your set of coins.
   • For every new coin found, update a "simulated" DP table to ensure future values match the input. If a provided value is smaller than what your current coins can achieve, the input is inconsistent.

4. Example explanation

Input: sum 1: 1, sum 2: 1, sum 3: 2, sum 4: 2

1. At 1: Value is 1. Coin {1} found.
2. At 2: Value is 1. Coin {2} found.
3. At 3: Value is 2. My coins {1, 2} can make 3 using $2+1$ (2 coins). Matches input.
4. At 4: Value is 2. My coins {1, 2} can make 4 using $2+2$ (2 coins). Matches input. Original coins: {1, 2}.

5. Common mistakes candidates make

• Simulating every combination: Trying to solve it as a subset-sum problem which is $O(2^N)$.
• Ignoring consistency: Failing to verify that the reconstructed coins actually produce the rest of the provided values.
• Sorting: Forgetting that coins must be discovered in increasing order of their values.

6. Interview preparation tip

When asked to "invert" an algorithm, always write down the forward recurrence first. Seeing the forward logic dp[i] = f(dp[i-coin]) makes it much easier to see that the coins are the "base cases" where the function returns its minimal non-zero value.