Inverse Coin Change - Practice Coding Problems

Inverse Coin Change - Problem

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.

Input & Output

Example 1 — Basic Case

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

› Output: [1,2]

💡 Note: With coins [1,2]: ways to make 1=1 (coin 1), ways to make 2=1 (coin 2), ways to make 3=2 (1+1+1 or 1+2), ways to make 4=2 (1+1+1+1 or 2+2), ways to make 5=3 (add coin 1 or 2 to make 4 or 3), ways to make 6=4 (multiple combinations)

Example 2 — Single Coin

$ Input: numWays = [1,0,0,1]

› Output: [1,4]

💡 Note: With coins [1,4]: ways to make 1=1 (coin 1), ways to make 2=0 (impossible), ways to make 3=0 (impossible), ways to make 4=1 (coin 4)

Example 3 — No Valid Set

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

› Output: []

💡 Note: No valid coin set can produce this pattern - the growth is too rapid for any reasonable denomination set

Constraints

1 ≤ numWays.length ≤ 1000
0 ≤ numWays[i] ≤ 1000
Each denomination value is at most numWays.length

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Given numWays array representing ways to make each amount

Pattern Detection

Identify where new denominations are introduced

Denomination Recovery

Extract the original coin denominations

Key Takeaway

🎯 Key Insight: Analyze when actual ways exceed expected ways to identify required denominations

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to analyze the numWays pattern to identify which denominations must exist. Best approach uses DP pattern analysis to check if each position requires a new denomination. Time: O(n²), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming - Pattern Analysis	O(n²)	O(n)	Analyze the numWays pattern to identify necessary denominations
Optimized - Greedy Reconstruction	O(n³)	O(n)	Identify denominations by analyzing the numWays pattern greedily
Brute Force - Try All Combinations	O(2^n × n²)	O(n²)	Generate all possible coin denomination sets and test each one

Dynamic Programming - Pattern Analysis — Algorithm Steps

Analyze differences between consecutive numWays values
Identify positions where new denominations are introduced
Validate by reconstructing the entire array

Visualization

Tap to expand

Step-by-Step Walkthrough

Analyze Pattern

Look at each position in numWays array

Compare Expected vs Actual

If actual > expected, new denomination needed

Add Denomination

Add the denomination and continue analysis

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* coinChange(int* coins, int coinSize, int target) {
    int* dp = (int*)calloc(target + 1, sizeof(int));
    dp[0] = 1;
    for (int i = 0; i < coinSize; i++) {
        for (int amount = coins[i]; amount <= target; amount++) {
            dp[amount] += dp[amount - coins[i]];
        }
    }
    return dp;
}

int* solution(int* numWays, int numWaysSize, int* returnSize) {
    if (numWaysSize == 0) {
        *returnSize = 0;
        return NULL;
    }
    
    int* denominations = (int*)malloc(numWaysSize * sizeof(int));
    int count = 0;
    
    for (int i = 1; i <= numWaysSize; i++) {
        if (numWays[i - 1] == 0) continue;
        
        int* currentDp;
        if (count == 0) {
            currentDp = (int*)calloc(i + 1, sizeof(int));
            currentDp[0] = 1;
        } else {
            currentDp = coinChange(denominations, count, i);
        }
        
        if (numWays[i - 1] > currentDp[i]) {
            denominations[count++] = i;
        }
        
        free(currentDp);
    }
    
    if (count > 0) {
        int* finalDp = coinChange(denominations, count, numWaysSize);
        for (int i = 1; i <= numWaysSize; i++) {
            if (finalDp[i] != numWays[i - 1]) {
                free(finalDp);
                *returnSize = 0;
                free(denominations);
                return NULL;
            }
        }
        free(finalDp);
    }
    
    *returnSize = count;
    return denominations;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int numWays[100];
    int size = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        numWays[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int returnSize;
    int* result = solution(numWays, size, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    if (result) free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Single pass through array (n) with coin change validation (n²)

⚠ Quadratic Growth

Space Complexity

O(n)

DP array for validation plus denomination storage

⚡ Linearithmic Space

23.0K Views

Medium Frequency

~35 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming - Pattern Analysis — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler