Formatted question description: https://leetcode.ca/all/1798.html
1798. Maximum Number of Consecutive Values You Can Make
Level
Medium
Description
You are given an integer array coins
of length n
which represents the n
coins that you own. The value of the i-th
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 * 10^4
1 <= coins[i] <= 4 * 10^4
Solution
Sort the array coins
. If the smallest value of coins
is greater than 1, return 1.
Otherwise, calculate the maximum consecutive integer value that can be made from coins
using a greedy approach. Initialize curr = 1
and index = 0
. If index < n
and coins[index] <= curr
, then add coins[index]
to curr
and increase index
. Repeat the process until the conditions do not hold, and return curr
.
class Solution {
public int getMaximumConsecutive(int[] coins) {
Arrays.sort(coins);
if (coins[0] > 1)
return 1;
int curr = 1;
int length = coins.length, index = 0;
while (true) {
if (index < length && coins[index] <= curr) {
curr += coins[index];
index++;
} else
break;
}
return curr;
}
}