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: coins = [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.
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|