the third one in Biweekly Contest 48.
Difficulty : Medium
Related Topics : Greedy
You are given an integer array
coins
of lengthn
which represents then
coins that you own. The value of thei
th
coin iscoins[i]
. You can make some valuex
if you can choose some of yourn
coins such that their values sum up tox
.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.
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.
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.
Input: nums = [1,4,10,3,1] Output: 20
coins.length == n
1 <= n <= 4 * 10^4
1 <= coins[i] <= 4 * 10^4
- mine
- Java
Runtime: 15 ms, faster than 100.00%, Memory Usage: 46.7 MB, less than 100.00% of Java online submissions
// O(N * Log(N))time // O(1)space public int getMaximumConsecutive(int[] coins) { Arrays.sort(coins); int t = 1; for(int i = 0; i < coins.length; i++){ if(coins[i] <= t){ t += coins[i]; }else{ break; } } return t; }
- Java