Maximum Number of Integers to Choose From a Range I

Maximum Number of Integers to Choose From a Range I

What is this problem about?

The Maximum Number of Integers to Choose From a Range I coding problem gives you a list of banned integers, a range [1, n], and a sum limit maxSum. You want to choose the maximum number of distinct integers from [1, n] that are not banned and whose total sum does not exceed maxSum.

Why is this asked in interviews?

Microsoft, PayPal, and Amazon include this problem as a clean greedy problem that tests set lookup and sequential selection. The optimal strategy is to always pick the smallest available unbanned integers first (to maximize count). Using a hash set for banned numbers makes the lookup O(1), enabling an O(n) greedy pass.

Algorithmic pattern used

Greedy with hash set: Store banned integers in a hash set. Iterate from 1 to n. For each integer, if it's not banned and adding it keeps the sum ≤ maxSum, include it. Stop when the sum would exceed maxSum or you've processed all integers. This greedy always picks smallest-first, maximizing count. Time: O(n + len(banned)).

A binary search variant sorts non-banned integers and binary searches for the maximum prefix sum ≤ maxSum, but the linear greedy is simpler and equally correct.

Example explanation

banned = [1, 6, 5], n = 5, maxSum = 6.

• Available integers: 2, 3, 4 (1, 5 banned; 6 out of range).
• Pick 2: sum=2 ≤ 6. Count=1.
• Pick 3: sum=5 ≤ 6. Count=2.
• Pick 4: sum=9 > 6. Stop.
• Answer = 2.

Common mistakes candidates make

• Iterating over integers not in [1, n]: The banned list may contain values outside [1, n]. Only consider integers in range.
• Adding banned integers: The hash set check must precede the sum check — always verify the integer is not banned before considering it.
• Off-by-one: The range is [1, n] inclusive; missing either boundary changes the answer.

Interview preparation tip

For the Array Hash Table Sorting Binary Search Greedy interview pattern, whenever a problem says "pick maximum count subject to sum constraint, avoiding a banned set," greedy smallest-first is optimal. A sorted banned set can be skipped more efficiently, but the hash set approach is simpler to code under time pressure. Know both.