Welcome to Subscribe On Youtube

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

############

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

  • // OJ: https://leetcode.com/problems/maximum-number-of-consecutive-values-you-can-make/
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
    int getMaximumConsecutive(vector<int>& A) {
        int cnt = 1;
        sort(begin(A), end(A));
        for (int n : A) {
            if (n > cnt) break;
            cnt += n;
        }
        return cnt;
    }
};

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

############

# 1798. Maximum Number of Consecutive Values You Can Make
# https://leetcode.com/problems/maximum-number-of-consecutive-values-you-can-make/

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


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

All Problems

All Solutions