Beats 100% | Array | Solution for LeetCode#2554
\n\n# Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem requires us to count the maximum number of integers we can choose fro
![image.png](https://assets.leetcode.com/users/images/f8d85f3d-3a78-4bd3-915c-22d9b5acbc71_1733444866.9797547.png)\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires us to count the maximum number of integers we can choose from 1 to n, excluding the banned numbers, such that their sum doesn\'t exceed maxSum.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Create an array arr to mark banned numbers.\n2. Iterate through the banned array and mark those numbers in arr.\n3. Iterate from 1 to n:\n\t- Skip banned numbers.\n\t- Add each non-banned number to the sum.\n\t- If the sum exceeds maxSum, break the loop.\n\t- Increment the count for each valid number.\n4. Return the final count.\n\n# Complexity\n- Time complexity: O(banned.length + n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(10001)  [ ~O(1) ]\nWe use a fixed-size array of 10001 elements, which is considered constant space.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nclass Solution {\n    public int maxCount(int[] banned, int n, int maxSum) {\n        int[] arr=new int[10001];\n        for(int i=0; i<banned.length; i++){\n            arr[banned[i]]=1;\n        }\n\n        long sum=0;\n        int cnt=0;\n        for(int i=1; i<=n; i++){\n            if(arr[i]==1){continue;}\n            sum+=i;\n            if(sum>maxSum){\n               break;\n            }\n            cnt++;\n        }\n\n        return cnt;\n    }\n}\n```\n\n```cpp []\nclass Solution {\npublic:\n    int maxCount(vector<int>& banned, int n, int maxSum) {\n        // Create a set to mark banned numbers\n        unordered_set<int> bannedSet(banned.begin(), banned.end());\n        \n        long long sum = 0; // Track cumulative sum\n        int count = 0;     // Track count of valid numbers\n\n        // Iterate through 1 to n\n        for (int i = 1; i <= n; i++) {\n            if (bannedSet.count(i)) continue; // Skip banned numbers\n            sum += i; // Add current number to the sum\n            if (sum > maxSum) break; // Stop if sum exceeds maxSum\n            count++; // Increment count of valid numbers\n        }\n\n        return count; // Return the count of valid numbers\n    }\n};\n\n```\n```csharp []\npublic class Solution {\n    public int MaxCount(int[] banned, int n, int maxSum) {\n        int[] arr = new int[10001];\n        foreach (int num in banned) {\n            arr[num] = 1;\n        }\n\n        long sum = 0;\n        int cnt = 0;\n        for (int i = 1; i <= n; i++) {\n            if (arr[i] == 1) continue;\n            sum += i;\n            if (sum > maxSum) {\n                break;\n            }\n            cnt++;\n        }\n\n        return cnt;\n    }\n}\n```\n```Python3 []\nclass Solution:\n    def maxCount(self, banned: list[int], n: int, maxSum: int) -> int:\n        banned_set = set(banned)  # Use a set for quick lookups\n        total_sum = 0  # Track the cumulative sum\n        count = 0  # Track the count of valid numbers\n\n        for i in range(1, n + 1):\n            if i in banned_set:\n                continue  # Skip banned numbers\n            total_sum += i\n            if total_sum > maxSum:\n                break  # Stop if the sum exceeds maxSum\n            count += 1\n\n        return count\n\n```\n```Swift []\nclass Solution {\n    func maxCount(_ banned: [Int], _ n: Int, _ maxSum: Int) -> Int {\n        var arr = [Int](repeating: 0, count: 10001)\n        for num in banned {\n            arr[num] = 1\n        }\n        \n        var sum: Int64 = 0\n        var cnt = 0\n        for i in 1...n {\n            if arr[i] == 1 { continue }\n            sum += Int64(i)\n            if sum > Int64(maxSum) {\n                break\n            }\n            cnt += 1\n        }\n        \n        return cnt\n    }\n}\n```\n
['Array', 'Swift', 'Python', 'C++', 'Java', 'Python3', 'C#']