C++ || 2 different approaches w/ some variants || fast (138ms, 100%?)
TODO(heder): Insert cute meme to ask for up-votes. ;)\n\n# Approach 1: use a set and sweep\n\nThe approach for the following variants is always the same. We the
**TODO(heder): Insert cute meme to ask for up-votes. ;)**\n\n# Approach 1: use a set and sweep\n\nThe approach for the following variants is always the same. We the list of banned\nnumbers into a data structure that\'s faster to access and then we sweep the numbers\nfrom 1 to n while the sum is blow `maxSum`.\n\n## Variant 1: std::set (525 ms)\n\nWe can directly construct the set from the input vector.\n\n```cpp\n    static int maxCount(const vector<int>& banned_vector, const int n, const int maxSum) {\n        set<int> banned(begin(banned_vector), end(banned_vector));\n        \n        int sum = 0;\n        int ans = 0;\n        for (int i = 1; i <= n; ++i) {\n            if (sum + i > maxSum) break;\n            \n            if (banned.count(i)) continue;\n            \n            sum += i;\n            ++ans;\n        }\n        return ans;\n    }\n```\n\n## Variant 2: std::set, only insert numbers <= n (329 ms)\n\nNot inserting all the numbers yields a nice speedup.\n\n```cpp\n    static int maxCount(const vector<int>& banned_vector, const int n, const int maxSum) {\n        set<int> banned;\n        for (int b : banned_vector)\n            if (b <= n) banned.insert(b);\n        \n        int sum = 0;\n        int ans = 0;\n        for (int i = 1; i <= n; ++i) {\n            if (sum + i > maxSum) break;\n            \n            if (banned.count(i)) continue;\n            \n            sum += i;\n            ++ans;\n        }\n        return ans;\n    }\n```\n\n## Variant 3: std::unordered_set (253 ms)\n\nUsing a hash set instead of an ordered set yields and anther nice speedup.\n\n```cpp\n    static int maxCount(const vector<int>& banned_vector, const int n, const int maxSum) {\n        unordered_set<int> banned;\n        for (int b : banned_vector)\n            if (b <= n) banned.insert(b);\n        \n        int sum = 0;\n        int ans = 0;\n        for (int i = 1; i <= n; ++i) {\n            if (sum + i > maxSum) break;\n            \n            if (banned.count(i)) continue;\n            \n            sum += i;\n            ++ans;\n        }\n        return ans;\n    }\n```\n\n## Variant 4: set::bitset (138 ms)\n\nThe number range in the ```banned``` vector is quite limited, so we can use a ```std::bitset``` instead of a hash set, which gives us a nice speedup as well.\n\n```cpp\n    static int maxCount(const vector<int>& banned_vector, const int n, const int maxSum) {\n        bitset<10240> banned;\n        for (int b : banned_vector)\n            if (b <= n) banned[b] = true;\n        \n        int sum = 0;\n        int ans = 0;\n        for (int i = 1; i <= n; ++i) {\n            if (sum + i > maxSum) break;\n            \n            if (banned[i]) continue;\n            \n            sum += i;\n            ++ans;\n        }\n        return ans;\n    }\n```\n\n# Approach 2: sort and sweep (225ms)\n\nInstead of using an extra set we can sort the banned vector so we can sweep it easily too. The sweep code feels bit clumbsy, please let me know if you have a nicer approach.\n\n```cpp\n    static int maxCount(vector<int>& banned, const int n, const int maxSum) {\n        sort(begin(banned), end(banned));\n        \n        int sum = 0;\n        int ans = 0;\n        int b = 0;\n        for (int i = 1; i <= n; ++i) {\n            if (sum + i > maxSum) break;\n            \n            if (b < size(banned)) {\n                while (b < size(banned) && banned[b] < i) ++b;\n                \n                if (b < size(banned) && banned[b] == i) continue;\n            }\n            \n            sum += i;\n            ++ans;\n        }\n        return ans;\n    }\n```\n\n_As always: Feedback, questions, and comments are welcome. Leaving an up-vote sparks joy! :)_\n\n**p.s. Join us on the [LeetCode The Hard Way Discord Server](https://discord.gg/hFUyVyWy2E)!**\n
['C']