Problem

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 youcan make with your coins starting from and including _0.

Note that you may have multiple coins of the same value.

Examples

Example 1

1
2
3
4
5
6

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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

1
2

Input: coins = [1,4,10,3,1]
Output: 20

Constraints

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

Solution

Method 1 – Greedy + Sorting

Intuition

If you can make all values up to x, and the next smallest coin is c, you can extend the range to x + c if c <= x + 1. Otherwise, you can’t make x + 1. So, sort the coins and keep extending the range as long as possible.

Approach

  1. Sort the coins in ascending order.
  2. Initialize x = 0 (the maximum consecutive value you can make).
  3. For each coin:
    • If coin > x + 1, break (can’t make x + 1).
    • Else, add coin to x (extend the range).
  4. Return x + 1 (since we start from 0).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    int getMaximumConsecutive(vector<int>& coins) {
        sort(coins.begin(), coins.end());
        int x = 0;
        for (int c : coins) {
            if (c > x + 1) break;
            x += c;
        }
        return x + 1;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

import "sort"
func getMaximumConsecutive(coins []int) int {
    sort.Ints(coins)
    x := 0
    for _, c := range coins {
        if c > x+1 {
            break
        }
        x += c
    }
    return x + 1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

import java.util.*;
class Solution {
    public int getMaximumConsecutive(int[] coins) {
        Arrays.sort(coins);
        int x = 0;
        for (int c : coins) {
            if (c > x + 1) break;
            x += c;
        }
        return x + 1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    fun getMaximumConsecutive(coins: IntArray): Int {
        coins.sort()
        var x = 0
        for (c in coins) {
            if (c > x + 1) break
            x += c
        }
        return x + 1
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def getMaximumConsecutive(self, coins: list[int]) -> int:
        coins.sort()
        x = 0
        for c in coins:
            if c > x + 1:
                break
            x += c
        return x + 1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl Solution {
    pub fn get_maximum_consecutive(mut coins: Vec<i32>) -> i32 {
        coins.sort();
        let mut x = 0;
        for c in coins {
            if c > x + 1 {
                break;
            }
            x += c;
        }
        x + 1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    getMaximumConsecutive(coins: number[]): number {
        coins.sort((a, b) => a - b);
        let x = 0;
        for (const c of coins) {
            if (c > x + 1) break;
            x += c;
        }
        return x + 1;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), for sorting the coins.
  • 🧺 Space complexity: O(1), as we use only a few variables for computation.