Maximum Number of Consecutive Values You Can Make

Medium
1297.

Maximum Number of Consecutive Values You Can Make

Maximum Number of Consecutive Values You Can Make is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.

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 == n
  • 1 <= n <= 4 * 10^4
  • 1 <= coins[i] <= 4 * 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} coins
 * @return {number}
 */
var getMaximumConsecutive = function(coins) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 == n
  • 1 <= n <= 4 * 10^4
  • 1 <= coins[i] <= 4 * 10^4

Hints for Maximum Number of Consecutive Values You Can Make

  1. Hint 1

    Suppose you can already make every value in [0, x). What happens when you add a coin of value c?

  2. 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 when c <= x.

  3. Hint 3

    Process the coins from smallest to largest, growing x; stop at the first coin larger than x.

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

  1. Sort coins in increasing order and set reach = 1 (only 0 is makeable with no coins).
  2. For each coin c: if c > reach, stop; otherwise reach += c.
  3. 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 reach

Java

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