Code Implementation

class Solution:
    def getMaximumConsecutive(self, coins):
        coins.sort()
        max_reachable = 0
        for coin in coins:
            if coin > max_reachable + 1:
                break
            max_reachable += coin
        return max_reachable + 1
      

class Solution {
public:
    int getMaximumConsecutive(vector<int>& coins) {
        sort(coins.begin(), coins.end());
        int maxReachable = 0;
        for (int coin : coins) {
            if (coin > maxReachable + 1) break;
            maxReachable += coin;
        }
        return maxReachable + 1;
    }
};
      

class Solution {
    public int getMaximumConsecutive(int[] coins) {
        Arrays.sort(coins);
        int maxReachable = 0;
        for (int coin : coins) {
            if (coin > maxReachable + 1) break;
            maxReachable += coin;
        }
        return maxReachable + 1;
    }
}
      

var getMaximumConsecutive = function(coins) {
    coins.sort((a, b) => a - b);
    let maxReachable = 0;
    for (let coin of coins) {
        if (coin > maxReachable + 1) break;
        maxReachable += coin;
    }
    return maxReachable + 1;
};
      

Problem Description

You are given an array of positive integers called coins, where each element represents the denomination of a coin. You can use each coin at most once. Your goal is to determine the maximum number of consecutive positive integers (starting from 1) that you can form by summing up some subset of these coins.

In other words, starting from 1, how many consecutive values can you make using any combination of the coins, without skipping any numbers in between, and without reusing coins?

Key constraints:

• Each coin can be used at most once.
• You must start from 1 and count up as far as possible without gaps.
• There is exactly one valid answer for each input.

Thought Process

At first glance, it may seem like you need to try all possible subsets of coins and check which sums you can make, then look for the longest streak of consecutive numbers starting from 1. However, this would be extremely inefficient, especially as the number of coins grows.

Instead, we can look for a pattern. If you can make all values up to max_reachable, and you have a coin with value less than or equal to max_reachable + 1, you can extend the range of consecutive values you can make. But if the next coin is larger than max_reachable + 1, there will be a gap you cannot fill, and you must stop.

This leads to a greedy approach: always use the smallest available coins first, and keep track of the largest consecutive value you can reach so far.

Solution Approach

• Step 1: Sort the coins. This ensures we always consider smaller denominations first, which is crucial for building up the consecutive values from 1 upward without missing any possibilities.
• Step 2: Initialize a variable max_reachable to 0. This will keep track of the largest consecutive value we can currently form.
• Step 3: Iterate through the sorted coins.
  • For each coin, check if its value is greater than max_reachable + 1.
  • If it is, you cannot form max_reachable + 1, so you must stop.
  • If it is less than or equal to max_reachable + 1, add its value to max_reachable. This extends the range of consecutive sums you can make.
• Step 4: Return max_reachable + 1. This is the maximum number of consecutive values starting from 1 that you can make.

This approach is efficient because it only requires a single pass through the sorted coins, and at each step, you either extend your reach or know you must stop.

Example Walkthrough

Let's use the example coins = [1, 1, 1, 4].

• Sort the coins: [1, 1, 1, 4]
• Start with max_reachable = 0
• First coin is 1: 1 ≤ 0+1, so max_reachable = 0 + 1 = 1
• Second coin is 1: 1 ≤ 1+1, so max_reachable = 1 + 1 = 2
• Third coin is 1: 1 ≤ 2+1, so max_reachable = 2 + 1 = 3
• Fourth coin is 4: 4 ≤ 3+1, so max_reachable = 3 + 4 = 7

Therefore, you can make all values from 1 to 7. The answer is 7.

If instead the coins were [1, 3]:

• Sort: [1, 3]
• max_reachable = 0
• First coin: 1 ≤ 0+1, so max_reachable = 1
• Second coin: 3 > 1+1, so you can't form 2, and must stop. Answer is 2.

Time and Space Complexity

Brute-force approach: Generating all possible subsets and checking their sums would take O(2^n) time, where n is the number of coins. This is because each coin can be either included or not in a subset, leading to exponential growth.

Optimized (greedy) approach:

• Sorting the coins takes O(n log n) time.
• The single pass through the coins is O(n).
• Overall, the time complexity is O(n log n).
• Space complexity is O(1) if sorting is done in-place, or O(n) if a new array is created for sorting.

Summary

The problem is elegantly solved using a greedy approach: by always using the smallest coins first and tracking the largest consecutive sum you can make, you can quickly determine the maximum number of consecutive values possible. The key insight is recognizing when a gap occurs that cannot be filled, which immediately tells you where to stop. This leads to an efficient solution that avoids the exponential complexity of brute-force enumeration.