# Maximum Number of Consecutive Values You Can Make
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-number-of-consecutive-values-you-can-make)
Canonical: https://scaleengineer.com/dsa/problems/maximum-number-of-consecutive-values-you-can-make
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Infosys](https://scaleengineer.com/companies/infosys)
---
## Problem
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 == n`
* `1 <= n <= 4 * 104`
* `1 <= coins[i] <= 4 * 104`

# Approaches
## Brute Force using Subset Sum Generation
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.
**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, ...`).
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Initialize a `HashSet` called `reachableSums` and add `0` to it.
- Iterate through each `coin` in the input array `coins`.
- For each `coin`, create a temporary list of new sums to be added. Iterate through all existing sums in `reachableSums` and add `sum + coin` to the temporary list.
- Add all sums from the temporary list to `reachableSums`.
- After processing all coins, find the smallest non-negative integer `k` that is not in `reachableSums`. This can be done by checking for `0, 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`).

## Greedy Approach with Sorting
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.
**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)`.
**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.
### Explanation
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`.

```java
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;
    }
}
```
### Algorithm
- Sort the `coins` array in non-decreasing order.
- Initialize a variable `reachable = 0`. This tracks the maximum value `x` such that all integers from `0` to `x` can be formed.
- Iterate through the sorted `coins`. For each `coin`:
  - If `coin <= reachable + 1`, we can extend our range. Update `reachable` by adding the coin's value: `reachable += coin`.
  - If `coin > reachable + 1`, a gap appears at `reachable + 1`. We cannot make any more consecutive values. The number of consecutive values we have formed is `0, 1, ..., reachable`, which is `reachable + 1` values. We break the loop.
- Return `reachable + 1`.

# Solutions
### Java

```java
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;
  }
}

```

### Python

```python
class Solution:
    def getMaximumConsecutive(self, coins: List[int]) -> int: ans = 1 for v in sorted(coins): if v > ans: break ans += v return ans

```

### CPP

```cpp
class 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;
  }
};

```