[LeetCode] Maximum Number of Integers to Choose From a Range I

2554. Maximum Number of Integers to Choose From a Range I

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.

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
class Solution {
long long sum(long long l, long long r) {
return r * (r + 1) / 2 - l * (l - 1) / 2;
}
long long helper(long long mi, long long ma, long long k) {
long long l = mi, r = ma, res = l;
while(l <= r) {
long long m = l + (r - l) / 2;
long long s = sum(mi,m);
if(s <= k) {
res = max(res,m);
l = m + 1;
} else r = m - 1;
}
return res;
}
public:
int maxCount(vector<int>& A, int n, long long maxSum) {
A.push_back(n + 1);
A.push_back(n + 2);
sort(begin(A), end(A));
A.erase(unique(begin(A), end(A)), end(A));
while(A.back() > n + 2) A.pop_back();
int res = 0, now = 1;
for(int i = 0; i < A.size() - 1 and maxSum; i++) {
if(A[i] != now) {
if(maxSum < now) break;
long long pick = helper(now, A[i] - 1, maxSum);
res += pick - now + 1;
maxSum -= sum(now, pick);
}
now = A[i] + 1;
}
return res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2023/02/07/PS/LeetCode/maximum-number-of-integers-to-choose-from-a-range-i/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.