Minimum Number of Coins to be Added

Medium

Asked by:

5 views

Topics:

Greedy Algorithms

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

Try coding it in LeetCode

Minimum Number of Coins to be Added

Medium

Asked by:

5 views

Topics:

Greedy Algorithms

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the coins in the input array, and what is the range for the target sum?
Can the input array contain zero or negative values?
If it's impossible to reach the target sum, what should be returned? Should I return -1, null, or throw an exception?
Are duplicate coin values allowed in the input array, and if so, should I consider them as distinct coins or count them only once?
Is the array of existing coins guaranteed to be sorted, and if not, do I need to sort it first?

Brute Force Solution

Approach

The brute-force method to solve this coin problem involves systematically checking every possible combination of coin additions. We start with the smallest addition and incrementally consider larger additions until we fulfill the required target. This guarantees we'll find the absolute minimum number of coins needed, although it might take a while.

Here's how the algorithm would work step-by-step:

First, sort all the available coins in ascending order, this helps to know which is the next possible amount.
Check if we can reach the target amount without adding any new coins.
If we cannot, try adding a single coin that is equal to the smallest amount that is missing. Then recheck.
If it's still not enough, try adding another coin that is equal to the smallest amount that is missing. Then recheck again.
Keep going, adding one coin at a time, and checking each time if we can now reach every amount between zero and the target amount.
The number of coins that you added when you reach the target amount is the answer.

Code Implementation

def minimum_number_coins_to_add(coins, target):
    coins.sort()
    added_coins = 0
    reachable_value = 0

    while reachable_value < target:
        # If we can reach the next coin, extend reachable value.
        if not coins or coins[0] > reachable_value + 1:
            needed_coin = reachable_value + 1
            reachable_value += needed_coin
            added_coins += 1

        # Otherwise, use one of the given coins.
        else:
            reachable_value += coins[0]
            coins.pop(0)

        # Ensure we don't exceed the target in one step.
        reachable_value = min(reachable_value, target)

        # Sort coins so that we always use the smallest coin.
        coins.sort()

        # After each addition, check if we've reached target.
        if reachable_value >= target:
            return added_coins

    return added_coins

Big(O) Analysis

Time Complexity

O(target * n) – The algorithm involves iterating up to the target value, adding coins incrementally. In the worst case, we might need to add a coin for each missing value up to the target. For each coin added, we iterate through the sorted coin array (of size n) to check if the sum can be reached. Therefore, the time complexity is proportional to the target value multiplied by the number of available coins (n). This results in a Big O notation of O(target * n).

Space Complexity

O(1) – The algorithm primarily uses a few variables to track the number of added coins and potentially a target amount. Sorting the coins in place as the first step does not use auxiliary space. The rechecking process does not require additional data structures to store intermediate results or visited states; it's a recalculation based on the existing sorted coins. Therefore, the space used remains constant regardless of the number of coins provided as input, resulting in O(1) space complexity.

Optimal Solution

Approach

The problem asks us to find the fewest extra coins to add to an existing set so that we can make change for every amount from 1 to the target amount. The key insight is to sort the coins we already have and then iteratively determine the smallest amount we *cannot* currently make change for. Then we add a coin of that value to our set.

Here's how the algorithm would work step-by-step:

First, sort the coins you already have in increasing order.
Keep track of the largest amount you can currently make change for, starting from zero.
Go through the sorted list of coins one by one.
For each coin, if its value is bigger than one more than the largest amount you can currently make change for, then you need to add a new coin.
The value of the new coin should be one more than the largest amount you can currently make change for. This ensures you can now make change for that new amount.
Update the largest amount you can make change for. If you added a new coin, update it by the new coin's value, otherwise by the value of the existing coin.
If the value of the current coin is not bigger than one more than the largest amount you can make change for, then you can make change for the amount equal to the largest value plus this coin's value.
After you go through all the coins, if the largest amount you can make change for is less than the target amount, keep adding new coins with a value of one more than the largest amount until you can make change for the target amount.
The number of new coins you added is the answer.

Code Implementation

def minimum_coins_to_add(coins, target):    coins.sort()
    number_of_coins_added = 0
    reachable_amount = 0

    for coin in coins:
        # Add coins to reach values between reachable amount and current coin value
        while coin > reachable_amount + 1:
            reachable_amount += reachable_amount + 1
            number_of_coins_added += 1

            # Optimization to prevent infinite loop
            if reachable_amount >= target:
                return number_of_coins_added

        # Update reachable amount
        reachable_amount += coin

    # Add coins until we can reach the target
    while reachable_amount < target:
        # We always add one more than what we can reach
        number_of_coins_added += 1
        reachable_amount += reachable_amount + 1

    return number_of_coins_added

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation is sorting the input array of n coins initially, which takes O(n log n) time. The subsequent iteration through the sorted coins takes O(n) time in the worst case to determine and add new coins. The while loop at the end also takes O(n) time at worst if the target is much larger than the sum of coins. Therefore, the overall time complexity is determined by the sorting step, making it O(n log n).

Space Complexity

O(1) – The algorithm sorts the input array in-place, so it doesn't require extra space for a new array. It uses a few variables to track the largest amount we can make change for and the number of coins added. These variables consume constant space regardless of the input size N (the number of coins). Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Coins array is null or empty	Return 0 if the coins array is null or empty since no coins are available to supplement.
Target value is less than or equal to zero	Return 0 if the target is non-positive, as we don't need to add any coins.
Coins array contains negative or zero values	Filter out negative or zero values from the coins array as only positive coin denominations are meaningful and valid.
Coins array contains a single, large value exceeding target	If the smallest coin exceeds the target, then return 1; otherwise proceed with the algorithm.
Target can be achieved by the given coins without adding any	If the target is already achievable using the given coins, return 0.
Target is a large value and the given coins are all small	The algorithm should handle large targets efficiently (e.g., using a greedy approach where possible) without exceeding memory limits or causing integer overflow.
Integer overflow when calculating the sum of existing coins	Use long or appropriate data types to store the sum to prevent potential overflow when accumulating coin values.
Maximum sized input array	Consider the time complexity of the algorithm to ensure scalability with large input arrays, such as O(n log n) with sorting or O(n) using a dynamic programming approach.