We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Coins to be Added

Number: 3231

Difficulty: Medium

Paid? No

Companies: Flipkart

Problem Description

Given an array of coin values and a target value, determine 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] becomes obtainable as the sum of a subsequence of the coins.

Key Insights

  • This problem is similar to the "Patching Array" problem.
  • Sort the coins to process them in increasing order.
  • Maintain a running sum (current reachable range) that indicates you can form every value in [1, current_sum].
  • If the next coin is greater than current_sum + 1, then there is a gap that must be filled by adding a coin with value current_sum + 1.
  • Continue this greedy strategy until the reachable range covers the target.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting, where n is the number of coins. The subsequent processing is O(n). Space Complexity: O(1) additional space if sorting is done in place (ignoring the space for input).

Solution

The solution uses a greedy algorithm. First, sort the coins array. Then, using a pointer (or index) for the coins and a variable (current_sum) representing the maximum contiguous value that can be obtained (i.e., you can obtain every value in [1, current_sum]), iterate until current_sum is at least target. If the coin at the pointer is less than or equal to current_sum + 1, it extends the range; otherwise, add a coin of value current_sum + 1 to patch the gap. Increment the count for each coin added. This approach ensures that the minimum number of coins are added while extending the reachable range optimally.

Code Solutions

# Function to determine the minimum number of coins to add
def minCoinsToAdd(coins, target):
    coins.sort()  # Sort coins in non-decreasing order
    ans = 0  # Counter for coins added
    current_sum = 0  # Current maximum value obtainable (we can form all values in [1, current_sum])
    i = 0  # Index pointer for coins
    
    # Process until we can form every sum up to target
    while current_sum < target:
        # If the next coin is within reach to extend the contiguous sum range
        if i < len(coins) and coins[i] <= current_sum + 1:
            current_sum += coins[i]  # Extend the range by this coin
            i += 1  # Move to the next coin
        else:
            # Gap detected: add a coin with value current_sum + 1
            current_sum += (current_sum + 1)
            ans += 1  # Increment the count of coins added
    return ans

# Example usages:
print(minCoinsToAdd([1, 4, 10], 19))       # Expected output: 2
print(minCoinsToAdd([1, 4, 10, 5, 7, 19], 19))  # Expected output: 1
print(minCoinsToAdd([1, 1, 1], 20))         # Expected output: 3
← Back to All Questions