Maximum Number of Integers to Choose From a Range II

Maximum Number of Integers to Choose From a Range II - 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 Case

$ Input: banned = [2,6], n = 7, maxSum = 15

› Output: 4

💡 Note: We can choose [1,3,4,5]. These are not banned and sum to 13 ≤ 15. Cannot add 7 as 13+7=20 > 15.

Example 2 — Small Budget

$ Input: banned = [1,3], n = 4, maxSum = 4

› Output: 1

💡 Note: Available numbers are [2,4]. We can only pick 2 (sum=2 ≤ 4). Adding 4 would make sum=6 > 4.

Example 3 — All Numbers Available

$ Input: banned = [], n = 3, maxSum = 6

› Output: 3

💡 Note: No numbers are banned. We can pick [1,2,3] with sum=6 ≤ 6, selecting all 3 numbers.

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 sum limit maxSum

Greedy Selection

Pick smallest available numbers first to maximize count

Result

Maximum count of integers that satisfy all constraints

Key Takeaway

🎯 Key Insight: Greedy approach works because smaller numbers allow more selections within the sum limit

Asked in

M Microsoft 12 a Amazon 8 G Google 5

The key insight is to use a greedy approach: always pick the smallest available numbers first to maximize count. Create a set of banned numbers for O(1) lookup, then iterate from 1 to n, adding each non-banned number until the sum would exceed maxSum. Best approach is greedy selection with Time: O(n + m), Space: O(m).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with Set	O(n + m)	O(m)	Create banned set, then greedily select smallest available numbers
Binary Search on Answer	O((n + m) log n)	O(m)	Binary search on the count of integers we can select

Brute Force with Set — Algorithm Steps

Step 1: Convert banned array to set for fast lookup
Step 2: Iterate from 1 to n, skip banned numbers
Step 3: Add each valid number to sum, count selections
Step 4: Stop when adding next number would exceed maxSum

Visualization

Tap to expand

Step-by-Step Walkthrough

Create Banned Set

Convert banned array to set for O(1) lookup

Iterate 1 to n

Check each number, skip if banned

Add if Within Budget

Add to selection if sum doesn't exceed maxSum

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 = (bool*)calloc(n + 1, sizeof(bool));
    
    for (int i = 0; i < bannedSize; i++) {
        if (banned[i] <= n) {
            isBanned[banned[i]] = true;
        }
    }
    
    int count = 0;
    int currentSum = 0;
    
    for (int i = 1; i <= n; i++) {
        if (!isBanned[i]) {
            if (currentSum + i <= maxSum) {
                currentSum += i;
                count++;
            } else {
                break;
            }
        }
    }
    
    free(isBanned);
    return count;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n + m)

Creating banned set takes O(m) time, iterating through range 1 to n takes O(n) time

✓ Linear Growth

Space Complexity

O(m)

Banned set stores up to m elements where m is length of banned array

✓ Linear Space

8.5K Views

Medium Frequency

~15 min Avg. Time

234 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 with Set — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler