C || C++ || Java || Python3 || Easy and Simple Solution with Explaination
The problem requires counting the maximum number of integers from 1 to n that are not banned and whose cumulative sum does not exceed maxSum. My initial thought
The problem requires counting the maximum number of integers from 1 to n that are not banned and whose cumulative sum does not exceed maxSum. My initial thought was to iterate through the numbers systematically, keeping track of valid numbers and their sum while avoiding banned numbers.\n\n# Approach\n1. Create a set of banned numbers for efficient O(1) lookup\n2. Initialize a count and sum tracker\n3. Iterate through numbers from 1 to n\n4. Skip banned numbers\n5. Stop adding numbers if the current sum plus the next number exceeds maxSum\n6. Count the number of valid integers added\n\nThe key steps involve:\n- Efficient filtering of banned numbers\n- Tracking cumulative sum\n- Stopping when maxSum is about to be exceeded\n\n# Complexity\n- Time complexity: $$O(n)$$\n  - We iterate through numbers from 1 to n once\n  - Set operations (creation and lookup) are O(1)\n  - The entire process takes linear time proportional to n\n\n- Space complexity: $$O(m)$$\n  - Where m is the number of banned numbers\n  - We create a set to store banned numbers\n  - The additional space used is directly proportional to the number of banned integers\n\n\n# Code\n``` C []\nint maxCount(int* banned, int bannedSize, int n, int maxSum) {\n   int* bannedSet = calloc(n + 1, sizeof(int));\n   for (int i = 0; i < bannedSize; i++) {\n       if (banned[i] <= n) {\n           bannedSet[banned[i]] = 1;\n       }\n   }\n   \n   int count = 0;\n   int sum = 0;\n   \n   for (int i = 1; i <= n; i++) {\n       if (bannedSet[i]) continue;\n       \n       if (sum + i > maxSum) break;\n       \n       sum += i;\n       count++;\n   }\n   \n   free(bannedSet);\n   \n   return count;\n}\n```\n```cpp []\nclass Solution \n{\npublic:\n    int maxCount(vector<int>& banned, int n, int maxSum) \n    {\n        unordered_set<int> ans(banned.begin(),banned.end());\n        int count=0;  \n        int sum=0; \n        int i=1; \n        while(i<=n&&sum+i<=maxSum)\n        {\n            if(ans.find(i)==ans.end())\n            {\n                cout<<i<<endl;\n                count++;\n                sum+=i;\n            }\n            i++;\n        }\n        return count;\n    }\n};\n```\n``` Java []\nclass Solution \n{\n    public int maxCount(int[] banned, int n, int maxSum) \n{\n        Set<Integer> bannedSet = new HashSet<>();\n        for (int num : banned) {\n            bannedSet.add(num);\n        }\n        \n        int count = 0;\n        int sum = 0;\n        \n        for (int i = 1; i <= n; i++) {\n            if (bannedSet.contains(i)) continue;\n            \n            if (sum + i > maxSum) break;\n            \n            sum += i;\n            count++;\n        }\n        \n        return count;\n    }\n}\n```\n```Python3 []\nclass Solution:\n    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n        banned_set = set(banned)\n        \n        count = 0\n        sum_total = 0\n        \n        for i in range(1, n + 1):\n            if i in banned_set:\n                continue\n            \n            if sum_total + i > maxSum:\n                break\n            \n            sum_total += i\n            count += 1\n        \n        return count\n```
['Array', 'Hash Table', 'Binary Search', 'Greedy', 'C', 'Sorting', 'C++', 'Java', 'Python3']