LeetCode 1798: Maximum Number of Consecutive Values You Can Make

Explanation

To solve this problem, we can use a Greedy approach. We need to find the maximum number of consecutive integer values that can be made starting from 0 using the given coins.

The key insight is that if we can make values from 0 to k-1, and we have a coin of value k, then we can also make values from k to 2k-1.

We can sort the given coins and iterate through them. For each coin, we check if we can make the next value starting from 0. If we can, we update the maximum consecutive value we can make.

At the end of the iteration, we will have the maximum number of consecutive integer values we can make.

Time complexity: O(n log n) where n is the number of coins (due to sorting) Space complexity: O(1)

import java.util.Arrays;

class Solution {
    public int getMaximumConsecutive(int[] coins) {
        Arrays.sort(coins);
        int max = 0;
        for (int coin : coins) {
            if (coin > max + 1) {
                break;
            }
            max += coin;
        }
        return max + 1;
    }
}