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

Maximum Number of Consecutive Values You Can Make

Number: 1930

Difficulty: Medium

Paid? No

Companies: Infosys

Problem Description

Given an array of coins, determine the maximum number of consecutive integer values (starting from 0) that can be formed using any subset of these coins. A value x can be formed if some of the coins add up exactly to x.

Key Insights

  • Sort the coins to process smaller values first.
  • Maintain a running sum (denoted as maxReach) which represents the maximum consecutive value that can be formed so far.
  • When processing a coin, if its value is greater than maxReach + 1, you cannot form maxReach + 1.
  • Otherwise, add the coin's value to maxReach, extending the range of consecutively formable values.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the coins. Space Complexity: O(1) or O(n) depending on the sorting algorithm used.

Solution

The solution leverages a greedy approach. We first sort the coins. Then, we iterate through each coin while maintaining a variable (maxReach) which represents the highest consecutive value that can be formed. If a coin is greater than maxReach + 1, it indicates a gap, and we cannot form the next consecutive value. Otherwise, we extend maxReach by the coin's value. This approach ensures we cover every possible consecutive value until an unfillable gap is encountered.

Code Solutions

# Define the function to compute max consecutive values
def getMaximumConsecutive(coins):
    # Sort the coins in non-decreasing order
    coins.sort()
    
    # Initialize maxReach to 0, representing the current maximum consecutive sum we can form
    maxReach = 0
    
    # Process each coin in the sorted list
    for coin in coins:
        # If the coin value is greater than maxReach+1, then there is a gap,
        # and we cannot form maxReach+1.
        if coin > maxReach + 1:
            break
        # Otherwise, update maxReach by adding the coin's value
        maxReach += coin
    
    # The maximum number of consecutive values that can be made is maxReach + 1 (including 0)
    return maxReach + 1

# Example usage:
coins = [1, 4, 10, 3, 1]
print(getMaximumConsecutive(coins))  # Expected output: 20
← Back to All Questions