1798. Maximum Number of Consecutive Values You Can Make (Leetcode)

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

Example: 2

Input: coins = [1,1,1,4]

Output: 8

Example: 3

Input: [1,4,10,3,1]

Output: 20

Constraints:

• coins.length == n
• 1 <= n <= 4 * 10 ^ 4
• 1 <= coins[i] <= 4 * 10 ^ 4

Algorithm intuition I (Using ranges):

• Let us consider that initially we can generate only 0(by not using any coin) using the coins we have. So let's say that we can generate all values from 0 upto 0 initially, (i.e [0, 0]).
• Now let's say we have to add a coin to denomination(say x)... so the range of coins we can generate now using x becomes -> [0 + x, 0 + x].
• From the above we can see that, if previous range [0, 0] and current range [0, x] touch each other(i.e right of first range + 1 == left of second range) or overlap each other... then we can generate all values from 0 to x and the range becomes [0, x]. And if they don't touch each other or overlap, then we cannot add this coin to the current range.

Algorithm intuition II (Array should be sorted):

• Also, since we are expanding current [0, 0] range to some [0, x] range... we should consider smallest value first. This is because if we use a bigger coin at first, it can potentially give rise to a non-overlapping range... and thus giving us wrong answer
• Consider the following example. coins = [2, 4, 1].
• If we were to add 2 to the range [0, 0], we will get the range [2, 2]. Since [0, 0] and [2, 2] don't overlap or touch each other... we cannot use coin 2 and so this coin will get wasted.
• But if we first used 1 and then 2 and then 4... we could have covered the range [0, 7].
• The simulation of above statement will be : [0, 0] -> [0, 1] -> [0, 3] -> [0, 7].
• Since it is required to add the smallest coin first, it is right to have our array sorted beforehand.

Full Code (Java): class Solution { public int getMaximumConsecutive(int[] coins) { // initial position int left = 0, right = 0; // sort the array Arrays.sort(coins); for(int i = 0; i < coins.length; i++) { int newLeft = coins[i]; int newRight = right + coins[i]; // checking if [left, right] and [newLeft, newRight] // overlaps or touch each other if(newLeft - 1 <= right) { // expanding the current range left = newLeft; right = newRight; } else { break; } } return right + 1; } }