Minimum Number of Coins to be Added - Practice Coding Problems

Minimum Number of Coins to be Added - Problem

You are given a 0-indexed integer array coins, representing the values of the coins available, and an integer target.

An integer x is obtainable if there exists a subsequence of coins that sums to x.

Return the minimum number of coins of any value that need to be added to the array so that every integer in the range [1, target] is obtainable.

A subsequence of an array is a new non-empty array that is formed from the original array by deleting some (possibly none) of the elements without disturbing the relative positions of the remaining elements.

Input & Output

Example 1 — Basic Case

$ Input: coins = [1,3], target = 6

› Output: 1

💡 Note: We can make sums 1, 3, 4 initially. Missing: 2, 5, 6. Add coin 2 to make all sums 1-6 possible: 1, 2, 3, 4(1+3), 5(2+3), 6(1+2+3).

Example 2 — Already Complete

$ Input: coins = [1,2,3], target = 7

› Output: 0

💡 Note: With coins 1,2,3 we can make all sums 1 to 7: 1, 2, 3, 4(1+3), 5(2+3), 6(1+2+3), 7(1+3+3 or others). No additions needed.

Example 3 — Large Gap

$ Input: coins = [1,5,10], target = 20

› Output: 2

💡 Note: Can make 1, 5, 6, 10, 11, 15, 16. Missing many sums. Need to add coins 2 and 4 to fill gaps efficiently.

Constraints

1 ≤ coins.length ≤ 10⁵
1 ≤ coins[i] ≤ 10⁴
1 ≤ target ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Given coins and target, find what sums are missing

Gap Detection

Identify gaps in achievable sum coverage

Optimal Addition

Add minimum coins to fill all gaps

Key Takeaway

🎯 Key Insight: Sort coins and track maximum achievable sum - add coins only when gaps are found

Asked in

G Google 12 a Amazon 8 M Microsoft 6

The key insight is that if we can make all sums from 1 to k, then adding a coin of value k+1 allows us to make all sums from 1 to 2k+1. The greedy approach sorts coins and tracks the maximum achievable sum, adding coins only when gaps are found. Time: O(n log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy - Sort and Fill Gaps	O(n log n)	O(1)	Sort coins and greedily track maximum achievable sum, adding coins when gaps are found
Brute Force - Check All Combinations	O(2^n × target)	O(target)	For each amount 1 to target, try all coin combinations to see if it's makeable

Greedy - Sort and Fill Gaps — Algorithm Steps

Sort coins array
Track maximum achievable sum
When gap found, add coin equal to maxAchievable + 1

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Coins

Process coins in ascending order

Track Coverage

Maintain maximum achievable sum

Fill Gaps

Add coins when gaps are found

Code -

solution.c — C

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

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int solution(int* coins, int coinsSize, int target) {
    qsort(coins, coinsSize, sizeof(int), compare);
    
    int added = 0;
    int maxAchievable = 0;
    int i = 0;
    
    while (maxAchievable < target) {
        if (i < coinsSize && coins[i] <= maxAchievable + 1) {
            maxAchievable += coins[i];
            i++;
        } else {
            // Gap found - add coin with value maxAchievable + 1
            maxAchievable += maxAchievable + 1;
            added++;
        }
    }
    
    return added;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int coins[1000];
    int coinsSize = 0;
    
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        coins[coinsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int target;
    scanf("%d", &target);
    
    int result = solution(coins, coinsSize, target);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting dominates the time complexity, iteration through coins is O(n)

⚡ Linearithmic

Space Complexity

O(1)

Only using a few variables to track state, no extra data structures

✓ Linear Space

28.4K Views

Medium Frequency

~25 min Avg. Time

892 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

Greedy - Sort and Fill Gaps — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler