Problem Description

You need to choose integers from the range [1, n] to maximize the count of chosen integers while following these constraints:

• Each integer from 1 to n can be chosen at most once
• You cannot choose any integer that appears in the banned array
• The sum of all chosen integers must not exceed maxSum

The goal is to return the maximum number of integers you can choose.

For example, if n = 7, banned = [2, 5], and maxSum = 10, you could choose integers like 1, 3, 4 (sum = 8) or 1, 3, 6 (sum = 10). The maximum count would be 3 integers.

The solution approach uses binary search to efficiently find the maximum number of consecutive integers that can be selected from each valid range. By adding boundaries 0 and n+1 to the banned list and sorting it, the code creates intervals of valid integers between banned numbers. For each interval [i+1, j-1], it uses binary search to find how many consecutive integers starting from i+1 can be selected without exceeding the remaining maxSum. The sum of the first k integers starting from i+1 is calculated using the arithmetic series formula: (first + last) * count / 2, which equals (i+1 + i+k) * k / 2.

Intuition

To maximize the count of integers we can choose, we should prioritize selecting smaller integers since they contribute less to the sum. This greedy approach allows us to fit more integers within the maxSum constraint.

The key insight is that between any two banned numbers, we have a continuous range of valid integers. For instance, if banned = [3, 7] and n = 10, we have valid ranges: [1, 2], [4, 6], and [8, 10]. Within each range, we want to select as many consecutive integers as possible starting from the smallest.

By adding boundaries 0 and n+1 to the banned list, we ensure that we also consider the ranges at the beginning [1, first_banned-1] and at the end [last_banned+1, n]. After sorting the banned list, each pair of adjacent banned numbers defines a range of selectable integers.

For each range [i+1, j-1] between banned numbers i and j, we need to find the maximum number of consecutive integers we can select starting from i+1 without exceeding the remaining maxSum. Since we're selecting consecutive integers, their sum forms an arithmetic sequence. If we select k integers starting from i+1, the sum is (i+1) + (i+2) + ... + (i+k) = (i+1 + i+k) * k / 2.

Binary search is perfect here because if we can select k integers without exceeding maxSum, we can also select any number less than k. Conversely, if k integers exceed maxSum, any number greater than k will also exceed it. This monotonic property makes binary search the optimal approach to find the maximum k for each range.

Learn more about Greedy, Binary Search and Sorting patterns.

Solution Approach

The implementation follows these steps:

1. Add boundaries to banned array: We extend the banned array by adding 0 and n + 1. This ensures we can handle the ranges at the beginning [1, first_banned-1] and end [last_banned+1, n] uniformly with other ranges.

2. Deduplicate and sort: Convert banned to a set to remove duplicates, then sort it. This gives us a sorted list of unique banned values that we can iterate through in pairs.

3. Process each valid range: Using pairwise(ban), we iterate through consecutive pairs (i, j) in the sorted banned list. For each pair, the valid selectable range is [i+1, j-1].

4. Binary search for maximum selection: For each range, we use binary search to find the maximum number of consecutive integers we can select:

   • left = 0, right = j - i - 1 (maximum possible integers in the range)
   • The mid-point check uses the arithmetic sum formula: (i + 1 + i + mid) * mid // 2
   • If this sum is within maxSum, we can potentially select more integers (move left = mid)
   • Otherwise, we need to select fewer integers (move right = mid - 1)

5. Update running totals: After finding the maximum selectable count left for the current range:

   • Add left to our answer ans
   • Subtract the sum of selected integers from maxSum: maxSum -= (i + 1 + i + left) * left // 2

6. Early termination: If maxSum <= 0, we can't select any more integers, so we break the loop.

The arithmetic sum formula (i + 1 + i + left) * left // 2 calculates the sum of left consecutive integers starting from i + 1. This equals the sum of integers from i + 1 to i + left, which is (first_term + last_term) * count / 2.

The binary search ensures we find the optimal number of integers to select from each range in O(log n) time, making the overall solution efficient.

Example Walkthrough

Let's walk through the solution with n = 7, banned = [2, 5], and maxSum = 10.

Step 1: Add boundaries and sort

• Original banned: [2, 5]
• Add boundaries 0 and n+1: [0, 2, 5, 8]
• Already sorted, no duplicates to remove

Step 2: Process each valid range using pairwise iteration

Range 1: Between 0 and 2 → valid integers [1, 1]

• Binary search between 0 and 1 integers (since 2-0-1 = 1)
• Check mid=0: sum of 0 integers = 0 ≤ 10 ✓
• Check mid=1: sum of integer 1 = 1 ≤ 10 ✓
• Maximum: 1 integer (select 1)
• Update: ans = 1, maxSum = 10 - 1 = 9

Range 2: Between 2 and 5 → valid integers [3, 4]

• Binary search between 0 and 2 integers (since 5-2-1 = 2)
• Check mid=1: sum of integer 3 = 3 ≤ 9 ✓
• Check mid=2: sum of integers 3,4 = (3+4)×2/2 = 7 ≤ 9 ✓
• Maximum: 2 integers (select 3, 4)
• Update: ans = 1 + 2 = 3, maxSum = 9 - 7 = 2

Range 3: Between 5 and 8 → valid integers [6, 7]

• Binary search between 0 and 2 integers (since 8-5-1 = 2)
• Check mid=1: sum of integer 6 = 6 > 2 ✗
• Check mid=0: sum of 0 integers = 0 ≤ 2 ✓
• Maximum: 0 integers (cannot select any)
• Update: ans = 3, maxSum = 2

Final Answer: 3

The algorithm correctly identifies that we can select at most 3 integers: {1, 3, 4} with sum = 8, leaving room within maxSum = 10. Note that we prioritize smaller integers to maximize the count.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The time complexity is dominated by the following operations:

• sorted(set(banned)): Creating a set takes O(n) time, and sorting takes O(n log n) time where n is the length of the banned list
• The main loop iterates through consecutive pairs in the sorted banned list, which is O(n) iterations
• Inside each iteration, there's a binary search with O(log(j - i)) complexity. In the worst case, j - i can be proportional to the input parameter n, making it O(log n) per iteration
• Overall: O(n log n) for sorting + O(n × log n) for the loop with binary search = O(n × log n)

Space Complexity: O(n)

The space complexity comes from:

• banned.extend([0, n + 1]): This modifies the original list in-place but doesn't change the asymptotic space
• set(banned): Creates a new set with at most n + 2 elements, which is O(n)
• sorted(set(banned)): Creates a new sorted list from the set, also O(n) space
• The pairwise iterator and other variables use O(1) additional space
• Overall: O(n) space complexity

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow in Sum Calculation

Pitfall: When calculating the arithmetic sum (first_num + last_num) * mid // 2, the intermediate multiplication can cause integer overflow for large values, even though Python handles big integers automatically. In languages like Java or C++, this would cause incorrect results.

Solution: Rearrange the formula to minimize overflow risk:

# Instead of: (first_num + last_num) * mid // 2
# Use: first_num * mid + mid * (mid - 1) // 2

This calculates the same sum but reduces the magnitude of intermediate values.

2. Binary Search Boundary Error

Pitfall: Using the wrong binary search pattern when left < right. The code uses mid = (left + right + 1) >> 1 (ceiling division) with left = mid update, but forgetting the +1 would cause an infinite loop when left = right - 1.

Solution: Always match the binary search pattern correctly:

• If using left = mid, then mid = (left + right + 1) // 2 (ceiling)
• If using right = mid, then mid = (left + right) // 2 (floor)

3. Not Handling Duplicate Banned Numbers

Pitfall: If you forget to deduplicate the banned array with set(), the same banned number appearing multiple times would create invalid "gaps" of size 0, leading to incorrect calculations.

Solution: Always convert to set before sorting:

sorted_banned = sorted(set(banned))  # Deduplication is crucial

4. Incorrect Gap Calculation

Pitfall: When calculating the maximum numbers in a gap between current_banned and next_banned, using next_banned - current_banned instead of next_banned - current_banned - 1 would include the banned numbers themselves.

Solution: Remember that the valid range is [current_banned + 1, next_banned - 1], so the count is:

right = next_banned - current_banned - 1  # Exclude both boundaries

5. Early Termination Logic Flaw

Pitfall: Breaking immediately when maxSum == 0 might miss cases where subsequent gaps have zeros that could still be selected (though this specific problem starts from 1, not 0).

Solution: Only break when maxSum < 0 or ensure the termination condition matches the problem constraints:

if maxSum <= 0:  # Can't afford any positive integers
    break