2952. Minimum Number of Coins to be Added - Solution

The 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.

Example 1:

Input: coins = [1,4,10], target = 19
Output: 2
Explanation: We need to add coins 2 and 8. The resulting array will be [1,2,4,8,10].
It can be shown that all integers from 1 to 19 are obtainable from the resulting array, and that 2 is the minimum number of coins that need to be added to the array.

Example 2:

Input: coins = [1,4,10,5,7,19], target = 19
Output: 1
Explanation: We only need to add the coin 2. The resulting array will be [1,2,4,5,7,10,19].
It can be shown that all integers from 1 to 19 are obtainable from the resulting array, and that 1 is the minimum number of coins that need to be added to the array.

Example 3:

Input: coins = [1,1,1], target = 20
Output: 3
Explanation: We need to add coins 4, 8, and 16. The resulting array will be [1,1,1,4,8,16].
It can be shown that all integers from 1 to 20 are obtainable from the resulting array, and that 3 is the minimum number of coins that need to be added to the array.

Constraints:

1 <= target <= 10⁵
1 <= coins.length <= 10⁵
1 <= coins[i] <= target

Approach overview

Problem Overview: You are given an array of coin values and a target. The goal is to ensure every value in the range [1, target] can be formed using the coins. You may add new coin denominations, and the task is to determine the minimum number of coins required to guarantee full coverage.

Approach 1: Brute Force Enumeration (Exponential Time, High Space)

A naive strategy tries adding different coin denominations and repeatedly checks whether every value from 1 to target can be constructed using subset sums of the available coins. This requires generating combinations or dynamic programming states for all possible sums. The search space grows exponentially as new coins are introduced. Time complexity is roughly O(2^n + target·n) depending on implementation, and space complexity can reach O(target). This approach mainly helps build intuition about why additional coins expand reachable sums but is not practical for large targets.

Approach 2: Greedy Coverage Expansion (O(n log n) time, O(1) space)

The optimal strategy uses a greedy observation. Suppose you can already form every value in the range [1, miss). The variable miss represents the smallest value you cannot currently form. If the next available coin value is ≤ miss, you can extend the reachable range by adding that coin, updating the coverage to [1, miss + coin). If the next coin is greater than miss, a gap exists. The only way to fill it optimally is to add a new coin with value miss. This doubles the reachable range to [1, 2·miss). Repeat until the coverage exceeds target.

The coins must be processed in sorted order, so the algorithm starts by sorting the array. Then iterate once through the coins while maintaining the current coverage boundary. Each step either consumes an existing coin or inserts a new one that maximally expands coverage. Sorting dominates the complexity, giving O(n log n) time and O(1) additional space.

This greedy method works because adding the smallest missing value always maximizes the new reachable interval while minimizing the number of added coins. The technique is closely related to the classic "patching array" problem and appears frequently in greedy design discussions.

Since the algorithm relies on processing coins in ascending order and extending coverage ranges, it also ties into concepts from sorting and sequential processing of an array.

Recommended for interviews: The greedy coverage approach is the expected solution. Interviewers want to see the insight that maintaining the smallest unreachable value (miss) allows you to decide whether to consume a coin or add one. Discussing brute force briefly shows problem exploration, but implementing the greedy strategy demonstrates algorithmic maturity.

Approach 1: Greedy Approach

This approach involves using a greedy algorithm to incrementally increase the range of obtainable values. Starting with an initial range that can be obtained from the original set of coins, we add the smallest unobtainable coin to extend this range. The goal is to keep extending the range until it includes all numbers up to the target.

Python

def minCoinsToAdd(coins, target):
    coins.sort()
    current = 0
    i = 0
    adds = 0

    while current < target:
        if i < len(coins) and coins[i] <= current + 1:
            current += coins[i]
            i += 1
        else:
            current += current + 1
            adds += 1
    return adds

# Example usage
coins = [1, 4, 10]
target = 19
print(minCoinsToAdd(coins, target))

Java

import java.util.Arrays;

public class Solution {
    public int minCoinsToAdd(int[] coins, int target) {
        Arrays.sort(coins);
        long current = 0;
        int i = 0, adds = 0;

        while (current < target) {
            if (i < coins.length && coins[i] <= current + 1) {
                current += coins[i++];
            } else {
                current += current + 1;
                adds++;
            }
        }
        return adds;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] coins = {1,4,10};
        int target = 19;
        System.out.println(sol.minCoinsToAdd(coins, target));
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

int minCoinsToAdd(std::vector<int>& coins, int target) {
    std::sort(coins.begin(), coins.end());
    long long current = 0;
    int i = 0, adds = 0;

    while (current < target) {
        if (i < coins.size() && coins[i] <= current + 1) {
            current += coins[i++];
        } else {
            current += current + 1;
            adds++;
        }
    }
    return adds;
}

int main() {
    std::vector<int> coins = {1, 4, 10};
    int target = 19;
    std::cout << minCoinsToAdd(coins, target) << std::endl;
    return 0;
}

JavaScript

function minCoinsToAdd(coins, target) {
    coins.sort((a, b) => a - b);
    let current = 0;
    let i = 0, adds = 0;

    while (current < target) {
        if (i < coins.length && coins[i] <= current + 1) {
            current += coins[i++];
        } else {
            current += current + 1;
            adds++;
        }
    }
    return adds;
}

// Example usage
const coins = [1, 4, 10];
const target = 19;
console.log(minCoinsToAdd(coins, target));

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

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

int minCoinsToAdd(int* coins, int coinsSize, int target) {
    qsort(coins, coinsSize, sizeof(int), compare);
    long long current = 0;
    int i = 0, adds = 0;

    while (current < target) {
        if (i < coinsSize && coins[i] <= current + 1) {
            current += coins[i++];
        } else {
            current += current + 1;
            adds++;
        }
    }
    return adds;
}

int main() {
    int coins[] = {1, 4, 10};
    int target = 19;
    int size = sizeof(coins) / sizeof(coins[0]);
    printf("%d\n", minCoinsToAdd(coins, size, target));
    return 0;
}

using System;
using System.Linq;

public class Solution {
    public int MinCoinsToAdd(int[] coins, int target) {
        Array.Sort(coins);
        long current = 0;
        int i = 0, adds = 0;

        while (current < target) {
            if (i < coins.Length && coins[i] <= current + 1) {
                current += coins[i++];
            } else {
                current += current + 1;
                adds++;
            }
        }
        return adds;
    }

    public static void Main() {
        int[] coins = {1, 4, 10};
        int target = 19;
        Solution sol = new Solution();
        Console.WriteLine(sol.MinCoinsToAdd(coins, target));
    }
}

The Python solution follows a greedy approach by making incremental progress on the sum achievable, starting from zero. The smallest unobtainable sum is identified incrementally, adding appropriate new coins to extend the range until the target range is entirely reachable.

Complexity

Time Complexity: O(n log n) for sorting. The space complexity is O(1) apart from input storage.

Try this approach in the editor

Approach 2: Greedy + Construction

Suppose the current amount we need to construct is s, and we have already constructed all amounts in [0,...,s-1]. If there is a new coin x, we add it to the array, which can construct all amounts in [x, s+x-1].

Next, we discuss in two cases:

If x \le s, then we can merge the two intervals above to get all amounts in [0, s+x-1].
If x \gt s, then we need to add a coin with a face value of s, so that we can construct all amounts in [0, 2s-1]. Then we consider the size relationship between x and s and continue to analyze.

Therefore, we sort the array coins in ascending order, and then traverse the coins in the array from small to large. For each coin x, we discuss in the above two cases until s > target.

The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the length of the array.

TypeScript

function minimumAddedCoins(coins: number[], target: number): number {
    coins.sort((a, b) => a - b);
    let ans = 0;
    for (let i = 0, s = 1; s <= target; ) {
        if (i < coins.length && coins[i] <= s) {
            s += coins[i++];
        } else {
            s <<= 1;
            ++ans;
        }
    }
    return ans;
}

func minimumAddedCoins(coins []int, target int) (ans int) {
	slices.Sort(coins)
	for i, s := 0, 1; s <= target; {
		if i < len(coins) && coins[i] <= s {
			s += coins[i]
			i++
		} else {
			s <<= 1
			ans++
		}
	}
	return
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Greedy Approach	Time Complexity: O(n log n) for sorting. The space complexity is O(1) apart from input storage.
Greedy + Construction	–

Complexity analysis

Approach	Time	Space	When to Use
Brute Force Enumeration	Exponential / O(2^n)	O(target)	Conceptual understanding of subset sums and coverage gaps
Greedy Coverage Expansion	O(n log n)	O(1)	Optimal solution when coins can be sorted and processed sequentially

Frequently asked questions

Is Minimum Number of Coins to be Added easy or hard?

The problem is rated Medium because the implementation is simple but the greedy insight is not immediately obvious. Recognizing that tracking the smallest missing value guarantees optimal coverage is the key observation.

Minimum Number of Coins to be Added Python/Java solution

Implement the greedy approach by sorting the coins array and maintaining the miss variable. Iterate through coins and expand coverage if coin ≤ miss; otherwise add a new coin equal to miss and increase the count. The same logic translates directly across Python, Java, C++, C#, and JavaScript.

How to solve Minimum Number of Coins to be Added in O(n)?

If the coins are already sorted, the greedy coverage algorithm runs in O(n) time. Maintain a variable miss representing the smallest unreachable value. Iterate through the coins and either extend coverage using the current coin or insert a new coin equal to miss to double the reachable range.

What is the best approach for Minimum Number of Coins to be Added?

The greedy coverage expansion approach is the optimal solution. Track the smallest value that cannot currently be formed (miss). If the next coin is less than or equal to miss, extend the reachable range; otherwise add a coin equal to miss. This guarantees the maximum coverage growth with the fewest added coins.

Is Minimum Number of Coins to be Added asked at Google/Amazon/Meta?

Greedy coverage and patching-style problems appear in interviews at companies like Google, Amazon, and Meta. Variants of this question test whether candidates understand how to maintain reachable ranges and make optimal greedy decisions when gaps appear.

What data structure is used in Minimum Number of Coins to be Added?

The problem primarily uses an array combined with a greedy strategy. After sorting the array, the algorithm iterates through it while maintaining a numeric boundary (miss) that represents the smallest unreachable sum.

What is the time complexity of Minimum Number of Coins to be Added?

The optimal greedy algorithm runs in O(n log n) time due to sorting the coins array. The subsequent scan through the coins is linear. Space complexity is O(1) since only a few variables are maintained while expanding the reachable range.

Minimum Number of Coins to be Added solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach

Approach 2: Greedy + Construction

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Minimum Number of Coins to be Added solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach

Approach 2: Greedy + Construction

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems