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 <= 1041 <= banned[i], n <= 1041 <= maxSum <= 109
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; } } // Solution 2 class Solution { public int maxCount(int[] banned, int n, int maxSum) { Set<Integer> black = new HashSet<>(); black.add(0); black.add(n + 1); for (int x : banned) { if (x < n + 2) { black.add(x); } } List<Integer> ban = new ArrayList<>(black); Collections.sort(ban); int ans = 0; for (int k = 1; k < ban.size(); ++k) { int i = ban.get(k - 1), j = ban.get(k); int left = 0, right = j - i - 1; while (left < right) { int mid = (left + right + 1) >>> 1; if ((i + 1 + i + mid) * 1L * mid / 2 <= maxSum) { left = mid; } else { right = mid - 1; } } ans += left; maxSum -= (i + 1 + i + left) * 1L * left / 2; if (maxSum <= 0) { break; } } 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; } }; // Solution 2 class Solution { public: int maxCount(vector<int>& banned, int n, int maxSum) { banned.push_back(0); banned.push_back(n + 1); sort(banned.begin(), banned.end()); banned.erase(unique(banned.begin(), banned.end()), banned.end()); banned.erase(remove_if(banned.begin(), banned.end(), [&](int x) { return x > n + 1; }), banned.end()); int ans = 0; for (int k = 1; k < banned.size(); ++k) { int i = banned[k - 1], j = banned[k]; int left = 0, right = j - i - 1; while (left < right) { int mid = left + ((right - left + 1) / 2); if ((i + 1 + i + mid) * 1LL * mid / 2 <= maxSum) { left = mid; } else { right = mid - 1; } } ans += left; maxSum -= (i + 1 + i + left) * 1LL * left / 2; if (maxSum <= 0) { break; } } 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 # Solution 2 class Solution: def maxCount(self, banned: List[int], n: int, maxSum: int) -> int: banned.extend([0, n + 1]) ban = sorted(x for x in set(banned) if x < n + 2) ans = 0 for i, j in pairwise(ban): left, right = 0, j - i - 1 while left < right: mid = (left + right + 1) >> 1 if (i + 1 + i + mid) * mid // 2 <= maxSum: left = mid else: right = mid - 1 ans += left maxSum -= (i + 1 + i + left) * left // 2 if maxSum <= 0: break 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 } // Solution 2 func maxCount(banned []int, n int, maxSum int) (ans int) { banned = append(banned, []int{0, n + 1}...) sort.Ints(banned) ban := []int{} for i, x := range banned { if (i > 0 && x == banned[i-1]) || x > n+1 { continue } ban = append(ban, x) } for k := 1; k < len(ban); k++ { i, j := ban[k-1], ban[k] left, right := 0, j-i-1 for left < right { mid := (left + right + 1) >> 1 if (i+1+i+mid)*mid/2 <= maxSum { left = mid } else { right = mid - 1 } } ans += left maxSum -= (i + 1 + i + left) * left / 2 if maxSum <= 0 { break } } 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 } } -
class Solution { public int maxCount(int[] banned, int n, int maxSum) { Set<Integer> black = new HashSet<>(); black.add(0); black.add(n + 1); for (int x : banned) { if (x < n + 2) { black.add(x); } } List<Integer> ban = new ArrayList<>(black); Collections.sort(ban); int ans = 0; for (int k = 1; k < ban.size(); ++k) { int i = ban.get(k - 1), j = ban.get(k); int left = 0, right = j - i - 1; while (left < right) { int mid = (left + right + 1) >>> 1; if ((i + 1 + i + mid) * 1L * mid / 2 <= maxSum) { left = mid; } else { right = mid - 1; } } ans += left; maxSum -= (i + 1 + i + left) * 1L * left / 2; if (maxSum <= 0) { break; } } return ans; } } -
class Solution { public: int maxCount(vector<int>& banned, int n, int maxSum) { banned.push_back(0); banned.push_back(n + 1); sort(banned.begin(), banned.end()); banned.erase(unique(banned.begin(), banned.end()), banned.end()); banned.erase(remove_if(banned.begin(), banned.end(), [&](int x) { return x > n + 1; }), banned.end()); int ans = 0; for (int k = 1; k < banned.size(); ++k) { int i = banned[k - 1], j = banned[k]; int left = 0, right = j - i - 1; while (left < right) { int mid = left + ((right - left + 1) / 2); if ((i + 1 + i + mid) * 1LL * mid / 2 <= maxSum) { left = mid; } else { right = mid - 1; } } ans += left; maxSum -= (i + 1 + i + left) * 1LL * left / 2; if (maxSum <= 0) { break; } } return ans; } }; -
int cmp(const void* a, const void* b) { return *(int*) a - *(int*) b; } int maxCount(int* banned, int bannedSize, int n, int maxSum) { qsort(banned, bannedSize, sizeof(int), cmp); int sum = 0; int ans = 0; for (int i = 1, j = 0; i <= n; i++) { if (sum + i > maxSum) { break; } if (j < bannedSize && i == banned[j]) { while (j < bannedSize && i == banned[j]) { j++; } } else { sum += i; ans++; } } return ans; } -
class Solution: def maxCount(self, banned: List[int], n: int, maxSum: int) -> int: banned.extend([0, n + 1]) ban = sorted(x for x in set(banned) if x < n + 2) ans = 0 for i, j in pairwise(ban): left, right = 0, j - i - 1 while left < right: mid = (left + right + 1) >> 1 if (i + 1 + i + mid) * mid // 2 <= maxSum: left = mid else: right = mid - 1 ans += left maxSum -= (i + 1 + i + left) * left // 2 if maxSum <= 0: break return ans -
func maxCount(banned []int, n int, maxSum int) (ans int) { banned = append(banned, []int{0, n + 1}...) sort.Ints(banned) ban := []int{} for i, x := range banned { if (i > 0 && x == banned[i-1]) || x > n+1 { continue } ban = append(ban, x) } for k := 1; k < len(ban); k++ { i, j := ban[k-1], ban[k] left, right := 0, j-i-1 for left < right { mid := (left + right + 1) >> 1 if (i+1+i+mid)*mid/2 <= maxSum { left = mid } else { right = mid - 1 } } ans += left maxSum -= (i + 1 + i + left) * left / 2 if maxSum <= 0 { break } } return }