Simple O(n) Approach
Intuition\n- Utilize a map to track banned numbers.\n- Iterate through numbers from 1 to n, checking if a number is banned and ensuring the cumulative sum doesn
# Intuition\n- Utilize a map to track banned numbers.\n- Iterate through numbers from 1 to `n`, checking if a number is banned and ensuring the cumulative sum doesn\'t exceed `maxSum`.\n\n# Approach\n1. Store banned numbers in a map for quick lookups.\n2. Initialize `sum` to keep track of the current sum and `cnt` to count valid numbers.\n3. Loop through numbers from 1 to `n`:\n   - Skip numbers present in the banned map.\n   - Check if adding the current number to the sum doesn\'t exceed `maxSum`.\n   - If valid, increment `cnt` and add the number to the sum.\n\n# Complexity\n- Time complexity: $$O(n)$$\n  - Iterating over the range from 1 to `n`.\n  - Map lookup for banned numbers is $$O(1)$$ (average case).\n- Space complexity: $$O(k)$$\n  - `k` is the size of the banned list.\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int maxCount(vector<int>& banned, int n, int maxSum) {\n        map<int, int> mp;\n        for(auto it: banned) {\n            mp[it]++;\n        }\n        int sum = 0, cnt = 0;\n        for(int i = 1; i <= n; i++) {\n            if(mp[i] == 0 && sum + i <= maxSum) {\n                cnt++;\n                sum += i;\n            }\n        }\n        return cnt;\n    }\n};\n```\n``` Java []\nimport java.util.HashSet;\n\nclass Solution {\n    public int maxCount(int[] banned, int n, int maxSum) {\n        HashSet<Integer> set = new HashSet<>();\n        for (int num : banned) {\n            set.add(num);\n        }\n        int sum = 0, count = 0;\n        for (int i = 1; i <= n; i++) {\n            if (!set.contains(i) && sum + i <= maxSum) {\n                count++;\n                sum += i;\n            }\n        }\n        return count;\n    }\n}\n\n```\n``` JavaScript []\nvar maxCount = function(banned, n, maxSum) {\n    const bannedSet = new Set(banned);\n    let sum = 0, count = 0;\n    for (let i = 1; i <= n; i++) {\n        if (!bannedSet.has(i) && sum + i <= maxSum) {\n            count++;\n            sum += i;\n        }\n    }\n    return count;\n};\n\n```\n``` Python []\nclass Solution:\n    def maxCount(self, banned: list[int], n: int, maxSum: int) -> int:\n        banned_set = set(banned)\n        sum_, count = 0, 0\n        for i in range(1, n + 1):\n            if i not in banned_set and sum_ + i <= maxSum:\n                count += 1\n                sum_ += i\n        return count\n\n```
['Python', 'C++', 'Java', 'Python3', 'JavaScript']