2557. Maximum Number of Integers to Choose From a Range II

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.

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) {
        sort(begin(A), end(A));
        A.push_back(n + 1);
        A.push_back(n + 2);
        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;
    }
};