Maximum Number of Consecutive Values You Can Make

Maximum Number of Consecutive Values You Can Make - 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 you can make with your coins starting from and including 0.

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

Input & Output

Example 1 — Basic Case

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

› Output: 3

💡 Note: You can make 0 (use no coins), 1 (use one coin), 2 (use both 1-coins), but cannot make 3. So consecutive values are [0,1,2] with count 3.

Example 2 — Single Coin

$ Input: coins = [1,3]

› Output: 2

💡 Note: You can make 0 (no coins), 1 (use coin 1), but cannot make 2. The coin 3 is too large to fill the gap. Count = 2.

Example 3 — Larger Gap

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

› Output: 8

💡 Note: With three 1's you can make [0,1,2,3]. Adding coin 4 extends to [0,1,2,3,4,5,6,7]. Count = 8.

Constraints

1 ≤ coins.length ≤ 4 × 10⁴
1 ≤ coins[i] ≤ 4 × 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Array of coin values [1,1,4]

Process

Find all possible sums and count consecutive from 0

Output

Maximum consecutive count: 3

Key Takeaway

🎯 Key Insight: Sort coins and greedily extend consecutive range - if coin ≤ current_reach+1, we can extend further

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Meta 6

The key insight is to sort coins first, then greedily extend the reachable range. If we can make values [0, reach-1] and encounter a coin ≤ reach, we can extend to [0, reach+coin-1]. Best approach is Greedy with Time: O(n log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Sort First Approach	O(n × sum)	O(sum)	Sort coins and use dynamic programming to track achievable sums
Greedy Optimal Solution	O(n log n)	O(1)	Sort coins and greedily extend the range of consecutive values
Brute Force - Try All Subsets	O(2ⁿ × n)	O(2ⁿ)	Generate all possible subset sums and count consecutive values from 0

Sort First Approach — Algorithm Steps

Sort coins in ascending order
Use DP array to track achievable sums
For each coin, update all possible new sums
Count consecutive integers from 0

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Coins

Sort coins: [1, 1, 4]

Build DP

Use DP to track all achievable sums

Count

Count consecutive integers from 0

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int solution(int* coins, int n) {
    if (n == 0) return 1;
    
    qsort(coins, n, sizeof(int), compare);
    int totalSum = 0;
    for (int i = 0; i < n; i++) {
        totalSum += coins[i];
    }
    
    // DP array to track achievable sums
    bool* dp = calloc(totalSum + 1, sizeof(bool));
    dp[0] = true;  // 0 is always achievable
    
    for (int i = 0; i < n; i++) {
        int coin = coins[i];
        // Iterate backwards to avoid using same coin multiple times
        for (int s = totalSum; s >= coin; s--) {
            if (dp[s - coin]) {
                dp[s] = true;
            }
        }
    }
    
    // Count consecutive integers starting from 0
    int count = 0;
    while (count <= totalSum && dp[count]) {
        count++;
    }
    
    free(dp);
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int coins[20];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL && n < 20) {
        coins[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(coins, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × sum)

For each of n coins, we iterate through sum possible values

✓ Linear Growth

Space Complexity

O(sum)

DP array to track achievable sums up to total sum

✓ Linear Space

24.5K Views

Medium Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sort First Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler