Maximum Number of Integers to Choose From a Range I

Leetcode Problem:

• Maximum Number of Integers to Choose From a Range I

Summary

• Find the maximum number of integers that can be chosen from the range [1, n] without exceeding maxSum and without being in the banned array.

Approach

• The approach used is to first create a boolean array ban to mark the banned numbers, then create a vector nums to store the available numbers, and finally use two pointers to find the maximum sum that does not exceed maxSum.

Complexity

• O(n + banned.length) where n is the range [1, n] and banned.length is the number of banned numbers

Explanation

• The code first initializes a boolean array ban to mark the banned numbers and a vector nums to store the available numbers
• Then it iterates over the banned numbers and marks them in the ban array
• After that, it iterates over the range [1, n] and adds the available numbers to the nums vector
• Finally, it uses two pointers to find the maximum sum that does not exceed maxSum by iterating over the nums vector and adding the current number to the sum
• If the sum exceeds maxSum, it breaks the loop and returns the number of available numbers that were added to the sum.

Solution Code:

class Solution {
public:
    vector nums;
    bool ban[10001];
    int maxCount(vector& banned, int n, int maxSum) {
        for(int i = 0 ; i < banned.size(); i++){
            ban[banned[i]] = true;
        }
        for(int i = 1; i <= n; i++){
            if(ban[i]) continue;
            nums.push_back(i);
        }
        int sum = 0;
        int ans = 0;
        for(int i = 0 ; i < nums.size(); i++){
            sum += nums[i];
            if(sum > maxSum) break;
            ans++;
        }
        return ans;
    }
};