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
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; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment