Question

1798. Maximum Number of Consecutive Values You Can Make

中文文档

Description

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: nums = [1,4,10,3,1]
Output: 20

 

Constraints:

• coins.length == n
• 1 <= n <= 4 * 104
• 1 <= coins[i] <= 4 * 104

Solutions

Solution 1: Sorting + Greedy

First, we sort the array. Then we define $ans$ as the current number of consecutive integers that can be constructed, initialized to $1$.

We traverse the array, for the current element $v$, if $v > ans$, it means that we cannot construct $ans+1$ consecutive integers, so we directly break the loop and return $ans$. Otherwise, it means that we can construct $ans+v$ consecutive integers, so we update $ans$ to $ans+v$.

Finally, we return $ans$.

The time complexity is $O(n \times \log n)$, and the space complexity is $O(\log n)$. Here, $n$ is the length of the array.

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

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 {
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;
  }
};

func getMaximumConsecutive(coins []int) int {
  sort.Ints(coins)
  ans := 1
  for _, v := range coins {
    if v > ans {
      break
    }
    ans += v
  }
  return ans
}

function getMaximumConsecutive(coins: number[]): number {
  coins.sort((a, b) => a - b);
  let ans = 1;
  for (const v of coins) {
    if (v > ans) {
      break;
    }
    ans += v;
  }
  return ans;
}