Maximum Number of Consecutive Values You Can Make
MedPrompt
You are given an integer array coins of length n which represents the n coins that you own. The value of the ith 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.
Example 1:
Input: coins = [1,3]
Output: 2
Explanation: You can make the following values:
- 0: take []
- 1: take [1]
You can make 2 consecutive integer values starting from 0.Example 2:
Input: coins = [1,1,1,4]
Output: 8
Explanation: You can make the following values:
- 0: take []
- 1: take [1]
- 2: take [1,1]
- 3: take [1,1,1]
- 4: take [4]
- 5: take [4,1]
- 6: take [4,1,1]
- 7: take [4,1,1,1]
You can make 8 consecutive integer values starting from 0.Example 3:
Input: coins = [1,4,10,3,1]
Output: 20
Constraints:
coins.length == n1 <= n <= 4 * 1041 <= coins[i] <= 4 * 104
Approaches
2 approaches with complexity analysis and trade-offs.
This approach is based on the classic subset sum problem. We generate every possible sum that can be formed by any combination of the given coins. We store these sums in a data structure, like a hash set, to keep track of all reachable values. After generating all possible sums, we find the smallest non-negative integer that is not present in our set of sums. This integer represents the number of consecutive values (from 0 up to that integer minus 1) that we can form.
Algorithm
- Initialize a
HashSetcalledreachableSumsand add0to it. - Iterate through each
coinin the input arraycoins. - For each
coin, create a temporary list of new sums to be added. Iterate through all existing sums inreachableSumsand addsum + cointo the temporary list. - Add all sums from the temporary list to
reachableSums. - After processing all coins, find the smallest non-negative integer
kthat is not inreachableSums. This can be done by checking for0, 1, 2, ...sequentially. - The first number not found is the result, as it represents the total count of consecutive values starting from 0 (i.e.,
0, 1, ..., k-1).
Walkthrough
We start by initializing a HashSet called reachableSums and add 0 to it, as a sum of 0 can always be made by choosing no coins. We then iterate through each coin in the input array coins. For each coin, we iterate through all the sums currently in reachableSums. For each existing sum, we calculate a newSum by adding the current coin's value to it (newSum = sum + coin). These newSum values are temporarily stored and then added to our main reachableSums set. This process effectively computes all possible subset sums. After processing all the coins, the reachableSums set contains every value that can be formed. Finally, we check for consecutive values starting from 0. We start with count = 0 and check if 0 is in the set, then 1, and so on. The first integer count that we cannot find in reachableSums is our answer.
import java.util.HashSet;import java.util.Set;import java.util.ArrayList;import java.util.List; class Solution { public int getMaximumConsecutive(int[] coins) { Set<Integer> reachableSums = new HashSet<>(); reachableSums.add(0); for (int coin : coins) { List<Integer> newSums = new ArrayList<>(); for (int sum : reachableSums) { // Check for potential integer overflow, though unlikely with problem constraints if (sum + coin >= 0) { newSums.add(sum + coin); } } reachableSums.addAll(newSums); } int maxConsecutive = 0; while (reachableSums.contains(maxConsecutive)) { maxConsecutive++; } return maxConsecutive; }}Complexity
Time
O(N * 2^N). In the worst-case scenario, the number of distinct sums can double with each new coin. The outer loop runs `N` times, and the inner loop runs `|reachableSums|` times, which can be up to `2^i` for the `i`-th coin.
Space
O(2^N). The `reachableSums` set can store up to `2^N` distinct values in the worst case (e.g., if coins are `1, 2, 4, 8, ...`).
Trade-offs
Pros
Conceptually simple and directly models the problem of finding all possible sums.
Cons
Extremely inefficient in both time and space.
Will result in Time Limit Exceeded (TLE) or Out of Memory Error for the given constraints.
A much more efficient approach is a greedy one. The key insight is that if we can already form all integer values from 0 to r, we want to pick the next coin c such that we can extend this range without creating a "gap". By sorting the coins first, we can process them in increasing order. This is optimal because smaller coins are more likely to help bridge the gap to the next consecutive integer, thus maximizing the range of consecutive values.
Algorithm
- Sort the
coinsarray in non-decreasing order. - Initialize a variable
reachable = 0. This tracks the maximum valuexsuch that all integers from0toxcan be formed. - Iterate through the sorted
coins. For eachcoin:- If
coin <= reachable + 1, we can extend our range. Updatereachableby adding the coin's value:reachable += coin. - If
coin > reachable + 1, a gap appears atreachable + 1. We cannot make any more consecutive values. The number of consecutive values we have formed is0, 1, ..., reachable, which isreachable + 1values. We break the loop.
- If
- Return
reachable + 1.
Walkthrough
Let's say we can form all values in the range [0, reachable]. Initially, we can only form 0 (by taking no coins), so we start with reachable = 0. To form the next value, reachable + 1, we need a coin or a combination of coins that sum to it. If we consider the next available coin c from our sorted list, and if c <= reachable + 1, we can now form all sums from c + 0 to c + reachable. This new range of sums [c, c + reachable] connects with our existing range [0, reachable]. The combined, continuous range becomes [0, reachable + c]. We can then update our reachable value to reachable + c. However, if the next coin c is greater than reachable + 1, we cannot form the value reachable + 1. A gap is formed, and we can't extend the consecutive sequence. At this point, the maximum number of consecutive values is reachable + 1.
import java.util.Arrays; class Solution { public int getMaximumConsecutive(int[] coins) { Arrays.sort(coins); int reachable = 0; for (int coin : coins) { if (coin <= reachable + 1) { reachable += coin; } else { break; } } return reachable + 1; }}Complexity
Time
O(N log N). The dominant operation is sorting the `coins` array. The subsequent loop runs once through the array, which takes `O(N)` time.
Space
O(log N) or O(N). This depends on the space complexity of the sorting algorithm used. In Java, `Arrays.sort` for primitives uses a dual-pivot quicksort, which has an average space complexity of `O(log N)`.
Trade-offs
Pros
Highly efficient and provides an optimal solution.
Simple to implement once the greedy insight is understood.
Cons
The main performance bottleneck is the initial sorting step.
Solutions
Solution
class Solution {public int getMaximumConsecutive(int[] coins) { Arrays.sort(coins); int ans = 1; for (int v : coins) { if (v > ans) { break; } ans += v; } return ans; }}class Solution: def getMaximumConsecutive(self, coins: List[int]) -> int: ans = 1 for v in sorted(coins): if v > ans: break ans += v return ansclass Solution {public: int getMaximumConsecutive(vector<int> &coins) { sort(coins.begin(), coins.end()); int ans = 1; for (int &v : coins) { if (v > ans) break; ans += v; } return ans; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.