Maximum Number of Integers to Choose From a Range I

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

Understanding the Visualization

Input Analysis

Range [1,n], banned numbers, and maxSum constraint

Greedy Selection

Pick smallest available numbers first

Count Result

Return total count of selected numbers

Key Takeaway

🎯 Key Insight: Greedily pick the smallest available numbers to maximize count within the sum budget

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

Approach	Time	Space	Notes
✓ Brute Force - Check All Combinations	O(2^n)	O(n)	Generate all possible combinations and find the maximum valid count
Greedy Selection with Hash Set	O(n + m)	O(m)	Use hash set for banned lookup and greedily pick smallest available numbers

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

⚠ Quadratic Growth

Space Complexity

O(n)

Store current subset and banned set

⚡ Linearithmic 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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler