Partial Sum + Binary Search
Partial Sum + Binary Search\nWe compute sum of elements [1..m]excluding banned elements. \n\nWe can do it in a constant time if we build a prefix sum of banned 
## Partial Sum + Binary Search\nWe compute sum of elements `[`1..m]` excluding banned elements. \n\nWe can do it in a constant time if we build a prefix sum of banned elements.\n\nWe binary-search for the largest m, which sum <= maxSum.\n\n**C++**\n```cpp\nint maxCount(vector<int>& ban, int n, int maxSum) {\n    int ps[10001] = {}, l = 0, r = n, cnt = 0;\n    for (int b : ban)\n        ps[b] = b;\n    partial_sum(begin(ps), end(ps), begin(ps));\n    while (l < r) {\n        if (int m = (l + r + 1) / 2; m * (m + 1) / 2 - ps[m] > maxSum)\n            r = m - 1;            \n        else\n            l = m;\n    }\n    for (int i = 0; i < l; ++i)\n        cnt += ps[i] != ps[i + 1];\n    return l - cnt;\n}\n```\n## Hashset\nThis solution is simpler, and asymptotically faster (O(n)) than the next one.\n\nFor OJ test cases, however, it is twice as slow as the second one, due to a hash set overhead.\n\n**C++**\n```cpp\nint maxCount(vector<int>& banned, int n, int maxSum) {\n    int res = 0;\n    unordered_set<int> s(begin(banned), end(banned));\n    for (int x = 1; x <= n && maxSum >= 0; ++x) \n        if (s.count(x) == 0) {\n            maxSum -= x;\n            res += maxSum >= 0;\n        }\n    return res;\n}\n```\n## Pointer\nWe sort the banned array, and, as we increase `x`, use a pointer `i` to check if a number is there.\n\nNote tha the array can contain duplicates, so we need to skip all of them. \n\n**C++**\n```cpp\nint maxCount(vector<int>& ban, int n, int maxSum) {\n    int i = 0, res = 0;\n    sort(begin(ban), end(ban));\n    for (int x = 1; x <= n && maxSum >= 0; ++x) {\n        if (i < ban.size() && ban[i] == x)\n            while (i < ban.size() && ban[i] == x)\n                ++i;\n        else {\n            maxSum -= x;\n            res += maxSum >= 0;\n        }\n    }\n    return res;\n}\n```
['C']