Use bitset to mark x in banned vs Sort+Math||beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nThis question is solved by Greedy. Look at the constraints\n> 1 <= banned.length <= 10^
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThis question is solved by Greedy. Look at the constraints\n> 1 <= banned.length <= 10^4\n1 <= banned[i], n <= 10^4\n1 <= maxSum <= 10^9\n\nA `bitset<10001>` is sufficient to replace the function of a hash set. Use bitset to mark x in banned(Python solution uses set)\n\n2nd approach uses sorting, arithmetic progression & the quadratic inequality; that solution is not fast but quite unique & Math.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Declare `bitset<10001> xNot=0`\n2. Use a loop to record `xNot[x]=1` for `x` in `banned`\n3. Initialize `sum=0, cnt=0`\n4. Proceed a loop from `x=1`, as long as `x<=n and sum<=maxSum` with step 1 (Greedy method)\n5. Within the loop to check if `!xNot[x]`, when true update `sum+=x` and `cnt++`\n6. If `sum<=maxSum` return `cnt` otherwise return `cnt-1`\n7.  Python code is made using set.\n# 1st Method similar to counting sort?\nYes. This question can be solved by using sort.\n\nLook the the structure of this algorithm, it is very similar to the procees applying the counting sort. First part to record `xNot` is similar to the counting part.\n\nSince the problem wants the maximum for `cnt` to make `sum` not exceeding `maxSum`, so just add up $x$ from 1 on to n and exclude `x` in `banned`. This procedure is very similar to counting sort.\n# Math used in 2nd Approach\n## Arithmetic Progression\nCompute $ sum=(p+1)+(p+2)+\\cdots +(x-1)$ Use the formula\n$$\nsum=\\frac{(x+p)(x-p-1)}{2}\n$$\n## Quadratic Inequality\nSolve $y^2+by+c\\leq 0$ with $y>0$\n$\\implies$ $y\\leq \\frac{-b+\\sqrt{b^2-4c}}{2} $\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n+m)$$ where $m=len(banned)$\nusing sort & quadratic formula: $O(m\\log m)$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(10001)$$\nusing sort & Math: $O(1)$\n# Code using bitset/set ||C++ 0ms beats 100%\n```cpp []\nclass Solution {\npublic:\n    int maxCount(vector<int>& banned, int n, int maxSum) {\n        bitset<10001> xNot=0;\n        for(int x: banned)\n            xNot[x]=1;\n        int sum=0, cnt=0;\n        for(int x=1; x<=n && sum<=maxSum; x++){\n            if (!xNot[x]){\n                sum+=x;\n                cnt++;\n            }\n        }\n        return (sum<=maxSum)?cnt:cnt-1;\n    }\n};\n```\n```Python []\nclass Solution:\n    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n        banned=set(banned)\n        sum, cnt=0, 0\n        for x in range(1, n+1):\n            if x not in banned:\n                sum+=x\n                if sum>maxSum: break\n                cnt+=1\n        return cnt\n```\n# C++ using sort & quadratic formula||43ms Beats 92.37%|| A similar method can be applied for solving 2195. Append K Integers With Minimal Sum \n```\nclass Solution {\npublic:\n    static int maxCount(vector<int>& banned, int n, int maxSum) {\n        banned.push_back(n+1);// make code easier\n        sort(banned.begin(), banned.end());\n        const int m=banned.size();\n        int prev=0, remain=maxSum, cnt=0;\n        for(int x: banned){\n            if (x>n+1) break;\n            if (x==prev) continue;\n            int d=x-prev-1;\n            int sum=(prev+x)*d/2;// arithmetic progression\n            if (sum<=remain){\n                cnt+=d;\n                remain-=sum;\n            }\n            else{\n                // Use quadratic formula to find largest y such that sum<=remain\n                int y=(-1+sqrt(1+4*((prev+1)*prev+2*remain)))/2.0;\n                cnt+=y-prev;\n                break;\n            }\n            prev=x;\n        }\n        return cnt;\n    }\n};\n\n\n\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n```
['Array', 'Hash Table', 'Math', 'Greedy', 'Bit Manipulation', 'Sorting', 'C++', 'Python3']