Maximum Number of Integers to Choose From a Range I - Problem

You are given an integer array banned and two integers n and maxSum. You are choosing some number of integers following the below rules:

The chosen integers have to be in the range [1, n].
Each integer can be chosen at most once.
The chosen integers should not be in the array banned.
The sum of the chosen integers should not exceed maxSum.

Return the maximum number of integers you can choose following the mentioned rules.

Input & Output

Example 1 — Basic Selection

$ Input: banned = [1,6,5], n = 5, maxSum = 6

› Output: 2

💡 Note: Available numbers are [2,3,4]. We can pick 2 and 4 (sum=6≤6) for maximum count of 2.

Example 2 — No Banned Numbers

$ Input: banned = [1,2,3,4,5,6,7], n = 8, maxSum = 1

› Output: 0

💡 Note: Only number 8 is available, but 8 > maxSum=1, so we can't pick any numbers.

Example 3 — Small Range

$ Input: banned = [11], n = 7, maxSum = 50

› Output: 7

💡 Note: Numbers [1,2,3,4,5,6,7] are all available. Sum = 1+2+3+4+5+6+7 = 28 ≤ 50, so pick all 7.

Constraints

1 ≤ banned.length ≤ 10⁴
1 ≤ banned[i], n ≤ 10⁴
1 ≤ maxSum ≤ 10⁹

Visualization

Tap to expand

Asked in

G Google 25 a Amazon 18 M Microsoft 15

The key insight is to greedily select the smallest available numbers to maximize count within the sum constraint. Best approach uses a hash set for O(1) banned number lookup and iterates from 1 to n. Time: O(n + m), Space: O(m).

Common Approaches

✓ Brute Force - Check All Combinations

⏱️ Time: O(2^n) Space: O(n)

Try every possible subset of integers from 1 to n, check if none are banned and sum doesn't exceed maxSum. This explores all 2^n possibilities to find the maximum count.

Greedy Selection with Hash Set

⏱️ Time: O(n + m) Space: O(m)

Store banned numbers in a hash set for O(1) lookup. Iterate from 1 to n, skip banned numbers, and greedily add the smallest available numbers until maxSum is exceeded.

Brute Force - Check All Combinations — Algorithm Steps

Generate all possible subsets of [1, n]
For each subset, check if any number is banned
Check if sum exceeds maxSum
Keep track of maximum valid count

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subsets

Create all 2^n possible combinations

Validate

Check banned numbers and sum constraint

Track Maximum

Keep the largest valid count

Code -

solution.c — C

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

int solution(int* banned, int bannedSize, int n, int maxSum) {
    bool isBanned[10001] = {false};
    for (int i = 0; i < bannedSize; i++) {
        if (banned[i] <= n) {
            isBanned[banned[i]] = true;
        }
    }
    
    int maxCount = 0;
    
    // Try all possible subsets using bit manipulation
    for (int mask = 0; mask < (1 << n); mask++) {
        int count = 0;
        int currentSum = 0;
        bool valid = true;
        
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                int num = i + 1;
                if (isBanned[num]) {
                    valid = false;
                    break;
                }
                count++;
                currentSum += num;
                if (currentSum > maxSum) {
                    valid = false;
                    break;
                }
            }
        }
        
        if (valid && count > maxCount) {
            maxCount = count;
        }
    }
    
    return maxCount;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse banned array
    int banned[1000];
    int bannedSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        int num = atoi(token);
        banned[bannedSize++] = num;
        token = strtok(NULL, "[,]");
    }
    
    int n, maxSum;
    scanf("%d", &n);
    scanf("%d", &maxSum);
    
    printf("%d\n", solution(banned, bannedSize, n, maxSum));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

Generate and check all 2^n possible subsets

✓ Linear Growth

Space Complexity

O(n)

Store current subset and banned set

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

890 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

Maximum Number of Integers to Choose From a Range I - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler