Welcome to Subscribe On Youtube
2554. Maximum Number of Integers to Choose From a Range I
Description
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.
Example 1:
Input: banned = [1,6,5], n = 5, maxSum = 6 Output: 2 Explanation: You can choose the integers 2 and 4. 2 and 4 are from the range [1, 5], both did not appear in banned, and their sum is 6, which did not exceed maxSum.
Example 2:
Input: banned = [1,2,3,4,5,6,7], n = 8, maxSum = 1 Output: 0 Explanation: You cannot choose any integer while following the mentioned conditions.
Example 3:
Input: banned = [11], n = 7, maxSum = 50 Output: 7 Explanation: You can choose the integers 1, 2, 3, 4, 5, 6, and 7. They are from the range [1, 7], all did not appear in banned, and their sum is 28, which did not exceed maxSum.
Constraints:
1 <= banned.length <= 10^{4}
1 <= banned[i], n <= 10^{4}
1 <= maxSum <= 10^{9}
Solutions
Solution 1: Greedy + Enumeration
We use the variable $s$ to represent the sum of the currently selected integers, and the variable $ans$ to represent the number of currently selected integers. We convert the array banned
into a hash table for easy determination of whether a certain integer is not selectable.
Next, we start enumerating the integer $i$ from $1$. If $s + i \leq maxSum$ and $i$ is not in banned
, then we can select the integer $i$, and add $i$ and $1$ to $s$ and $ans$ respectively.
Finally, we return $ans$.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Where $n$ is the given integer.
Solution 2: Greedy + Binary Search
If $n$ is very large, the enumeration in Method One will time out.
We can add $0$ and $n + 1$ to the array banned
, deduplicate the array banned
, remove elements greater than $n+1$, and then sort it.
Next, we enumerate every two adjacent elements $i$ and $j$ in the array banned
. The range of selectable integers is $[i + 1, j  1]$. We use binary search to enumerate the number of elements we can select in this range, find the maximum number of selectable elements, and then add it to $ans$. At the same time, we subtract the sum of these elements from maxSum
. If maxSum
is less than $0$, we break the loop. Return the answer.
The time complexity is $O(n \times \log n)$, and the space complexity is $O(n)$. Where $n$ is the length of the array banned
.

class Solution { public int maxCount(int[] banned, int n, int maxSum) { Set<Integer> ban = new HashSet<>(banned.length); for (int x : banned) { ban.add(x); } int ans = 0, s = 0; for (int i = 1; i <= n && s + i <= maxSum; ++i) { if (!ban.contains(i)) { ++ans; s += i; } } return ans; } }

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

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

func maxCount(banned []int, n int, maxSum int) (ans int) { ban := map[int]bool{} for _, x := range banned { ban[x] = true } s := 0 for i := 1; i <= n && s+i <= maxSum; i++ { if !ban[i] { ans++ s += i } } return }

function maxCount(banned: number[], n: number, maxSum: number): number { const set = new Set(banned); let sum = 0; let ans = 0; for (let i = 1; i <= n; i++) { if (i + sum > maxSum) { break; } if (set.has(i)) { continue; } sum += i; ans++; } return ans; }

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