• Posts

Problem 2952 Minimum Number of Coins to be Added

Problem Statement

Link - Problem 2952

Question

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 <= 105
• 1 <= coins.length <= 105
• 1 <= coins[i] <= target

Solution

class Solution {
public:
    int minimumAddedCoins(vector<int>& coins, int target) {
        sort(coins.begin(),coins.end());
        int missing = 1, result = 0, index = 0;
        while(missing<=target)
        {
            if(index<coins.size() && coins[index]<=missing)
            {
                missing += coins[index];
                index++;
            }
            else
            {
                missing += missing;
                result++;
            }
        }
        return result;

    }
};

Complexity Analysis

| Algorithm        | Time Complexity | Space Complexity |
| ---------------- | --------------- | ---------------- |
| Greedy Algorithm | O(n log n)      | O(1)             |

Explanation

Intial Thoughts

To start, we need to understand the concept of obtainable integers and subsequences of the given array. We should think about how the array can be modified to make all integers in the target range obtainable. We can begin by considering the minimum value that needs to be added to the array and how this addition can affect the obtainability of integers in the target range. Some key points to consider include:

1. Understanding the definition of an obtainable integer and its relation to the given array,
2. Identifying the role of the target value in determining the obtainability of integers,
3. Recognizing the need to add coins to the array to achieve obtainability,
4. Analyzing the importance of the starting value of 1 and how to proceed from there,
5. Developing a strategy to determine the minimum number of coins to be added

Intuitive Analysis

A more in-depth analysis involves considering the pattern of how numbers become obtainable when coins are added to the array. The given solution involves sorting the array and tracking the ‘missing’ value, which represents the smallest number that cannot be obtained. Some key intuitive steps include:

1. Sorting the array to understand the available coin values,
2. Iterating through the sorted array and identifying the ‘missing’ value,
3. Deciding whether to use an existing coin or add a new coin based on the ‘missing’ value,
4. Updating the ‘missing’ value accordingly and tracking the number of added coins,
5. Continuing this process until the ‘missing’ value exceeds the target, thereby ensuring all integers in the range are obtainable

1. Intuition

• The problem requires finding the minimum number of coins to add to the given array so that every integer in the range [1, target] is obtainable.
• To approach this problem, we need to think about the concept of obtainable numbers and how they can be formed using the given coins.
• The key insight is to start from the smallest possible obtainable number, which is 1, and try to extend it to the target.
• We can use a greedy approach to add the smallest possible coin that can help us extend the obtainable range.
• The solution works by maintaining a variable missing that keeps track of the smallest number that is not yet obtainable.
• The algorithm iteratively checks if the current missing number can be obtained using the given coins, and if not, it adds a new coin to the array.
• This process continues until all numbers up to the target are obtainable.

2. Implementation

• The solution starts by sorting the coins array in ascending order using sort(coins.begin(), coins.end()).
• It then initializes variables missing to 1, result to 0, and index to 0 to keep track of the smallest non-obtainable number, the number of coins added, and the current index in the coins array, respectively.
• The algorithm uses a while loop that continues until missing is greater than the target, and inside the loop, it checks if the current coins[index] is less than or equal to missing.
• If the condition is true, it updates missing by adding coins[index] to it and increments the index.
• If the condition is false, it updates missing by doubling it and increments the result by 1, effectively adding a new coin to the array.
• The solution finally returns the result, which represents the minimum number of coins that need to be added to the array.
• The time complexity of the solution is O(n log n) due to the sorting, where n is the number of coins, and the space complexity is O(1) as it only uses a constant amount of space.

Complexity Analysis

Time Complexity:

• The time complexity is O(n log n) due to the sort(coins.begin(),coins.end()) operation, which has a time complexity of O(n log n) for sorting the coins array. The subsequent while loop has a maximum of target iterations, but since the missing value doubles in each iteration where a coin is not used, the total number of iterations is logarithmic in the target value, making the overall time complexity dominated by the sorting operation.
• The dominant operations are the sorting of the coins array and the while loop that calculates the minimum number of coins needed. However, since the while loop has a maximum of logarithmic iterations, its impact on the overall time complexity is negligible compared to the sorting operation.
• Justification of Big O classification can be derived from the fact that the algorithm’s running time grows quadratically with the size of the input (n) due to the sorting operation, and the subsequent while loop does not significantly affect this growth. Hence, the time complexity is indeed O(n log n).

Space Complexity:

• The algorithm uses a constant amount of space to store variables such as missing, result, and index, resulting in a space complexity of O(1).
• The input array coins is sorted in-place, meaning that it does not require any additional space that scales with the input size, further justifying the O(1) space complexity.
• The overall space complexity is O(1) because the algorithm only uses a fixed amount of space, regardless of the size of the input array coins.

Footnote

This question is rated as Medium difficulty.

Hints

Sort the coins array and maintain the smallest sum that is unobtainable by induction.

If we don’t use any coins, the smallest integer that we cannot obtain by sum is 1. Suppose currently, for a fixed set of the first several coins the smallest integer that we cannot obtain is x + 1, namely we can form all integers in the range [1, x] but not x + 1.

If the next unused coin’s value is NOT x + 1 (note the array is sorted), we have to add x + 1 to the array. After this addition, we can form all values from x + 1 to 2 _ x + 1 by adding x + 1 in [1, x]’s formations. So now we can form all the numbers of [1, 2 _ x + 1]. After this iteration the new value of x becomes 2 * x + 1.

Similar Questions: