Maximum Number of Integers to Choose From a Range II

1
2
3
4

Input: banned = [1,4,6], n = 6, maxSum = 4
Output: 1
Explanation: You can choose the integer 3.
3 is in the range [1, 6], and do not appear in banned. The sum of the chosen integers is 3, which does not exceed maxSum.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

Input: banned = [4,3,5,6], n = 7, maxSum = 18
Output: 3
Explanation: You can choose the integers 1, 2, and 7.
All these integers are in the range [1, 7], all do not appear in banned, and their sum is 18, which does not exceed maxSum.
[]()```

### Constraints

- `1 <= banned.length <= 10^5`
- `1 <= banned[i] <= n <= 10^9`
- `1 <= maxSum <= 10^15`

## Solution

### Method 1 – Greedy + Skipping Banned Numbers

#### Intuition

To maximize the count of chosen numbers, always pick the smallest available number not in `banned` and keep adding until the sum exceeds `maxSum`. Skipping banned numbers ensures we only consider valid picks.

#### Approach

1. Add all banned numbers to a set for O(1) lookup.
2. Initialize `ans` (count) and `curr_sum` (current sum) to 0.
3. Iterate from 1 to `n`:
  - If the number is banned, skip it.
  - If adding the number to `curr_sum` exceeds `maxSum`, stop.
  - Otherwise, add the number to `curr_sum` and increment `ans`.
4. Return `ans`.

#### Code


    

         
         
         
        
            
            
        
            
            
                 
                 
                
                    Cpp 
                
            
        
            
            
        
            
            
                 
                 
                
                    Go 
                
            
        
            
            
        
            
            
                 
                 
                
                    Java 
                
            
        
            
            
        
            
            
                 
                 
                
                    Kotlin 
                
            
        
            
            
        
            
            
                 
                 
                
                    Python 
                
            
        
            
            
        
            
            
                 
                 
                
                    Rust 
                
            
        
            
            
        
    

    

        
         
        
        
         
         
        

             
            
             
            
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
            
            
            


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution {
public:
   int maxCount(vector<int>& banned, int n, int maxSum) {
      unordered_set<int> ban(banned.begin(), banned.end());
      int ans = 0;
      long long curr_sum = 0;
      for (int i = 1; i <= n; ++i) {
        if (ban.count(i)) continue;
        if (curr_sum + i > maxSum) break;
        curr_sum += i;
        ++ans;
      }
      return ans;
   }
};


        
        
        
         
        
        
         
         
        

             
            
             
            
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
            
            
            


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


func maxCount(banned []int, n int, maxSum int) int {
   ban := make(map[int]bool)
   for _, v := range banned {
      ban[v] = true
   }
   ans := 0
   currSum := 0
   for i := 1; i <= n; i++ {
      if ban[i] {
        continue
      }
      if currSum+i > maxSum {
        break
      }
      currSum += i
      ans++
   }
   return ans
}


        
        
        
         
        
        
         
         
        

             
            
             
            
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
            
            
            


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution {
   public int maxCount(int[] banned, int n, int maxSum) {
      Set<Integer> ban = new HashSet<>();
      for (int b : banned) ban.add(b);
      int ans = 0;
      long currSum = 0;
      for (int i = 1; i <= n; i++) {
        if (ban.contains(i)) continue;
        if (currSum + i > maxSum) break;
        currSum += i;
        ans++;
      }
      return ans;
   }
}


        
        
        
         
        
        
         
         
        

             
            
             
            
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
            
            
            


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution {
   fun maxCount(banned: IntArray, n: Int, maxSum: Int): Int {
      val ban = banned.toHashSet()
      var ans = 0
      var currSum = 0L
      for (i in 1..n) {
        if (i in ban) continue
        if (currSum + i > maxSum) break
        currSum += i
        ans++
      }
      return ans
   }
}


        
        
        
         
        
        
         
         
        

             
            
             
            
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
            
            
            


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution:
   def maxCount(self, banned: list[int], n: int, maxSum: int) -> int:
      ban = set(banned)
      ans = 0
      curr_sum = 0
      for i in range(1, n + 1):
        if i in ban:
           continue
        if curr_sum + i > maxSum:
           break
        curr_sum += i
        ans += 1
      return ans


        
        
        
         
        
        
         
         
        

             
            
             
            
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
                 
                     
                
            
            
            
            


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


use std::collections::HashSet;
impl Solution {
   pub fn max_count(banned: Vec<i32>, n: i32, max_sum: i64) -> i32 {
      let ban: HashSet<i32> = banned.into_iter().collect();
      let mut ans = 0;
      let mut curr_sum = 0i64;
      for i in 1..=n {
        if ban.contains(&i) { continue; }
        if curr_sum + i as i64 > max_sum { break; }
        curr_sum += i as i64;
        ans += 1;
      }
      ans
   }
}


        
        
        
         
        
        
    



#### Complexity

- ⏰ Time complexity: O(m + min(n, maxSum)), where m = banned.length. In practice, the loop stops early due to the sum constraint.
- 🧺 Space complexity: O(m) for the banned set.