Maximum Number of Consecutive Values You Can Make — Solution
Maximum Number of Consecutive Values You Can Make solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Maximum Number of Consecutive Values You Can Make is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Greedy
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You hold n coins with values coins[0], …, coins[n-1]. You can make a value x if some subset of your coins (each coin used at most once) adds up to exactly x; the empty subset makes 0.
Return how many consecutive integer values, starting from 0 and including it, you can make.
Example 1
Input: coins = [1,3]
Output: 2
Explanation: You can make 0 and 1, but not 2.
Example 2
Input: coins = [1,1,1,4]
Output: 8
Explanation: Every value from 0 to 7 can be made.
Example 3
Input: coins = [1,4,10,3,1]
Output: 20
Constraints
coins.length == n1 <= n <= 4 * 10^41 <= coins[i] <= 4 * 10^4
Hints for Maximum Number of Consecutive Values You Can Make
Hint 1
Suppose you can already make every value in
[0, x). What happens when you add a coin of valuec?Hint 2
You can now make every value in
[0, x)and in[c, c + x). These two ranges join into[0, x + c)exactly whenc <= x.Hint 3
Process the coins from smallest to largest, growing
x; stop at the first coin larger thanx.
How to solve Maximum Number of Consecutive Values You Can Make
Sort the coins and keep the invariant 'every value in [0, reach) can be made'; a coin c extends reach by c as long as c <= reach.
Approach
- Sort
coinsin increasing order and setreach = 1(only 0 is makeable with no coins). - For each coin
c: ifc > reach, stop; otherwisereach += c. - Return
reach.
Why it works
If [0, reach) is makeable and c <= reach, then adding c to each of those sums covers [c, c + reach), which overlaps or touches [0, reach), so [0, reach + c) is makeable. If the next coin in sorted order is larger than reach, every remaining coin is too, and any sum that uses one of them is at least reach + 1, while sums of the earlier coins only reach reach - 1 consecutively; so the value reach itself can never be made, and the count is reach.
Complexity
- Time —
O(n log n) - Space —
O(1) besides the sort
Pitfalls
- The count includes 0, so with coins
[2]the answer is 1, not 0. - Processing coins unsorted can stop too early at a large coin that a later small coin would have bridged.
- The total can reach 1.6·10^9 + 1 — still within int32, but do not add anything beyond it.
Reference solution
Python
from typing import List
def getMaximumConsecutive(coins: List[int]) -> int:
reach = 1
for c in sorted(coins):
if c > reach:
break
reach += c
return reachJava
public static int getMaximumConsecutive(int[] coins) {
int[] sorted = coins.clone();
Arrays.sort(sorted);
long reach = 1;
for (int c : sorted) {
if (c > reach) break;
reach += c;
}
return (int) reach;
}C++
int getMaximumConsecutive(vector<int>& coins) {
vector<int> sorted = coins;
sort(sorted.begin(), sorted.end());
long long reach = 1;
for (int c : sorted) {
if (c > reach) break;
reach += c;
}
return (int)reach;
}JavaScript
var getMaximumConsecutive = function(coins) {
var sorted = coins.slice().sort(function(a, b) { return a - b; });
var reach = 1;
for (var i = 0; i < sorted.length; i++) {
if (sorted[i] > reach) break;
reach += sorted[i];
}
return reach;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms