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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Consecutive Values You Can Make

Difficulty: Medium

Problem Description

You are given an integer array coins of length n which represents the n coins that you own. The value of the i-th coin is coins[i]. You can make some value x if you can choose some of your n coins such that their values sum up to x.

Return the maximum number of consecutive integer values that you can make with your coins starting from and including 0.

Note that you may have multiple coins of the same value.

Key Insights

  • The problem can be solved by leveraging the concept of greedy algorithms, where we try to make the smallest values possible first.
  • By sorting the coins and iterating through them, we can build consecutive sums starting from 0.
  • If at any point we encounter a coin whose value is greater than the current maximum consecutive sum we can form, we cannot make that sum, and thus we stop.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the coins. Space Complexity: O(1) since we are using a constant amount of extra space.

Solution

To solve this problem, we can use the following approach:

  1. Sort the array of coins.
  2. Initialize a variable to keep track of the maximum consecutive sum that can be formed, starting from 0.
  3. Iterate through the sorted array and for each coin:
    • If the coin's value is less than or equal to the current maximum consecutive sum + 1, update the maximum consecutive sum by adding the coin's value.
    • If the coin's value is greater than the current maximum consecutive sum + 1, we cannot create the next consecutive value, and we break out of the loop.
  4. The value of the maximum consecutive sum at the end of the iteration will be the answer.

Code Solutions

def max_consecutive_values(coins):
    coins.sort()  # Sort the coins
    max_consecutive = 0  # Initialize the maximum consecutive sum
    
    for coin in coins:
        # If the coin value is greater than max_consecutive + 1, we can't form the next consecutive value
        if coin > max_consecutive + 1:
            break
        max_consecutive += coin  # Update the maximum consecutive sum
    
    return max_consecutive + 1  # Include 0 in the count

# Example usage:
# print(max_consecutive_values([1, 3]))  # Output: 2
← Back to All Questions