You are given an integer array `coins`

of length `n`

which represents the `n`

coins that you own. The value of the `i`

coin is ^{th}`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:2Explanation: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:8Explanation: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:nums = [1,4,10,3,1]Output:20

**Constraints:**

`coins.length == n`

`1 <= n <= 4 * 10`

^{4}`1 <= coins[i] <= 4 * 10`

^{4}

**Solution: Greedy + Math**

We want to start with smaller values, sort input array in ascending order.

First of all, the first number has to be 1 in order to generate sum of 1.

Assuming the first i numbers can generate 0 ~ k.

Then the i+1-th number x can be used if and only if x <= k + 1, such that we can have a consecutive sum of k + 1 by adding x to a sum between [0, k] and the new maximum sum we have will be k + x.

Time complexity: O(nlogn)

Space complexity: O(1)

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 |
// Author: Huahua class Solution { public: int getMaximumConsecutive(vector<int>& coins) { sort(begin(coins), end(coins)); int ans = 0; for (int c : coins) { if (c > ans + 1) break; ans += c; } return ans + 1; } }; |