Maximum Number of Integers to Choose From a Range II

Maximum Number of Integers to Choose From a Range II

What is this problem about?

The Maximum Number of Integers to Choose From a Range II coding problem is the harder variant of Range I: same setup (banned list, range [1, n], maxSum) but the banned list and n can be much larger, requiring a more efficient solution than linear scan. You must use binary search over the sorted non-banned integers to find the maximum count efficiently.

Why is this asked in interviews?

PayPal includes this problem to test binary search proficiency in the context of filtered range queries. When n can be up to 10^9 but the banned list is small, a linear scan over [1, n] is infeasible. Candidates must binary search on the count k: "can I pick k unbanned integers from [1, n] with sum ≤ maxSum?" This tests both binary search design and prefix sum computation over ranges with holes.

Algorithmic pattern used

Binary search on count k: Sort banned integers (filter those in [1, n]). Binary search on the answer k. For a given k, compute the minimum possible sum of k non-banned integers from [1, n]: pick the k smallest available. Use the sorted banned list to figure out which integers are available using prefix count of banned values up to each point. The minimum sum of the first k non-banned integers can be computed in O(log(n) + |banned|) using prefix sums over the banned list.

Example explanation

banned = [2, 4], n = 6, maxSum = 10.

• Non-banned integers in [1,6]: 1, 3, 5, 6.
• k=1: min sum = 1 ≤ 10. Feasible.
• k=2: min sum = 1+3 = 4 ≤ 10. Feasible.
• k=3: min sum = 1+3+5 = 9 ≤ 10. Feasible.
• k=4: min sum = 1+3+5+6 = 15 > 10. Not feasible.
• Answer = 3.

Common mistakes candidates make

• Linear scan when n is huge: O(n) scan times out for n up to 10^9. Always binary search.
• Not filtering banned values outside [1, n]: These don't affect the answer and inflate the banned set unnecessarily.
• Incorrect minimum sum computation: The sum of the first k non-banned integers requires careful accounting of how many banned values fall before each integer.

Interview preparation tip

For the Array Sorting Binary Search Greedy interview pattern, compare Range I (small n, use linear scan) vs Range II (large n, binary search on count) — this is a common interview follow-up. When n is huge but the excluded set is small, "binary search on answer + compute feasibility using excluded set" is the go-to pattern. Practice this template for maximum count under sum constraints.