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.

Examples

Example 1

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.

Example 2

1
2
3
4

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.
  1. Return ans.

Code

 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.