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

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

✓ Binary Search on Answer

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

Use binary search to find the maximum count. For each candidate count, check if it's possible to select that many integers within the constraints.

Brute Force with Set

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

Convert banned array to set for O(1) lookup, then iterate from 1 to n, adding each non-banned number to our selection until we exceed maxSum.

Binary Search on Answer — Algorithm Steps

Step 1: Binary search on possible count values (0 to n)
Step 2: For each count, check if it's achievable
Step 3: Greedily pick smallest available numbers to test feasibility
Step 4: Return the maximum feasible count

Visualization

Tap to expand

Step-by-Step Walkthrough

Search Space

Binary search between 0 and n possible counts

Check Feasibility

For each count, test if achievable with greedy selection

Narrow Range

Adjust search range based on feasibility check

Code -

solution.c — C

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

bool canSelect(int count, bool* isBanned, int n, int maxSum) {
    int currentSum = 0;
    int selected = 0;
    
    for (int i = 1; i <= n; i++) {
        if (!isBanned[i]) {
            if (currentSum + i <= maxSum) {
                currentSum += i;
                selected++;
                if (selected == count) {
                    return true;
                }
            } else {
                break;
            }
        }
    }
    
    return selected >= count;
}

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 left = 0, right = n;
    int result = 0;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (canSelect(mid, isBanned, n, maxSum)) {
            result = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    free(isBanned);
    return result;
}

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) log n)

Binary search takes O(log n) iterations, each checking feasibility in O(n + m) time

✓ Linear Growth

Space Complexity

O(m)

Banned set stores up to m elements

✓ 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

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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search on Answer — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler