{x}
blog image

Maximum Number of Consecutive Values You Can Make

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 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: coins = [1,4,10,3,1]
Output: 20

 

Constraints:

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

Solution Explanation: 1798. Maximum Number of Consecutive Values You Can Make

This problem asks for the maximum number of consecutive integer values that can be made using a given set of coins. The key insight is that we can always make the value 0 (by selecting no coins). The goal is then to determine the largest consecutive sequence starting from 0.

Approach:

The most efficient approach uses a greedy strategy combined with sorting. Here's a breakdown:

  1. Sort the Coins: Sort the coins array in ascending order. This allows us to consider the smallest coins first. Sorting ensures we build up our possible sums efficiently.

  2. Greedy Construction: Initialize a variable ans to 1 (we can always make 0 and 1 if there's at least a coin with value 1). Iterate through the sorted coins array. For each coin value v:

    • If v is greater than ans, it means we cannot make the value ans. In this case, we've found the largest consecutive sequence possible, so we break the loop.
    • Otherwise (v <= ans), we can add the coin value to our reachable sum. We update ans to ans + v, extending the range of consecutive values we can create.

  3. Return the Result: The final value of ans represents the maximum number of consecutive integer values we can make, starting from 0.

Time Complexity: O(n log n), dominated by the sorting step. Space Complexity: O(log n) in the best and average cases for sorting (due to recursive calls in some sorting algorithms), or O(n) in the worst case (for example, using counting sort).

Code Implementation (Python):

class Solution:
    def getMaximumConsecutive(self, coins: List[int]) -> int:
        coins.sort()  # Sort the coins in ascending order
        ans = 1       # We can always make 0
        for coin in coins:
            if coin > ans:
                break  # We can't make 'ans', so we're done
            ans += coin  # Extend the range of consecutive values
        return ans

Code Implementation (Java):

import java.util.Arrays;
 
class Solution {
    public int getMaximumConsecutive(int[] coins) {
        Arrays.sort(coins); // Sort the coins
        int ans = 1;       // We can always make 0
        for (int coin : coins) {
            if (coin > ans) {
                break; // We can't make 'ans', so we're done
            }
            ans += coin; // Extend the range
        }
        return ans;
    }
}

Code Implementation (C++):

#include <algorithm>
#include <vector>
 
class Solution {
public:
    int getMaximumConsecutive(std::vector<int>& coins) {
        std::sort(coins.begin(), coins.end()); // Sort the coins
        int ans = 1;                          // We can always make 0
        for (int coin : coins) {
            if (coin > ans) {
                break; // We can't make 'ans', so we're done
            }
            ans += coin; // Extend the range
        }
        return ans;
    }
};

Code Implementation (Go):

import "sort"
 
func getMaximumConsecutive(coins []int) int {
	sort.Ints(coins) // Sort the coins
	ans := 1          // We can always make 0
	for _, coin := range coins {
		if coin > ans {
			break // We can't make 'ans', so we're done
		}
		ans += coin // Extend the range
	}
	return ans
}

Code Implementation (Javascript):

/**
 * @param {number[]} coins
 * @return {number}
 */
var getMaximumConsecutive = function(coins) {
    coins.sort((a,b) => a - b); //Sort the coins
    let ans = 1; //We can always make 0
    for(let coin of coins){
        if(coin > ans) break; //We can't make 'ans', so we're done
        ans += coin; //Extend the range
    }
    return ans;
};

These code examples all follow the same core algorithm. The choice of language impacts only the syntax and specific sorting function used. The overall time and space complexity remain consistent.