🔥BEATS 💯 % 🎯 |✨SUPER EASY BEGINNERS 👏
\n\n\n---\n\n# Intuition\nThe problem requires us to maximize the count of numbers chosen from \(1\) to \(n\) without exceeding a given maximum sum (\(maxSum\))
![image.png](https://assets.leetcode.com/users/images/74263eb4-4f39-4ee9-a6ea-47d078509165_1733469886.3802571.png)\n\n\n---\n\n# Intuition\nThe problem requires us to maximize the count of numbers chosen from \\(1\\) to \\(n\\) without exceeding a given maximum sum (\\(maxSum\\)), while also avoiding a set of banned numbers. The key is to iteratively pick numbers in ascending order (starting from \\(1\\)), skipping banned numbers, and stopping when adding the next number exceeds \\(maxSum\\).\n\n---\n\n# Approach\n1. **Use a Set for Banned Numbers:**  \n   Convert the list of banned numbers into a set for efficient lookups (\\(O(1)\\) average time complexity for checking membership).\n\n2. **Iterate Through Numbers:**  \n   Start iterating from \\(1\\) to \\(n\\). For each number:\n   - Skip the number if it is in the banned set.\n   - Check if adding the current number to the running sum exceeds \\(maxSum\\). If yes, stop the process.\n   - Otherwise, add the number to the sum and increment the count of numbers selected.\n\n3. **Return the Count:**  \n   Once the iteration ends (either because the sum limit is reached or \\(n\\) is exceeded), return the count of valid numbers.\n\n---\n\n# Complexity\n- **Time complexity:**  \n  $$O(n)$$ \u2014 We iterate through numbers from \\(1\\) to \\(n\\), and checking membership in the set takes \\(O(1)\\) for each number.\n\n- **Space complexity:**  \n  $$O(b)$$ \u2014 Space required to store the banned numbers in a set, where \\(b\\) is the size of the banned list.\n\n---\n\n\n```dart []\nclass Solution {\n  int maxCount(List<int> banned, int n, int maxSum) {\n    // Use a set for efficient lookups\n    Set<int> bannedSet = banned.toSet();\n\n    // Iterate through numbers 1 to n\n    int sum = 0, count = 0;\n    for (int i = 1; i <= n; i++) {\n      // Skip banned numbers\n      if (bannedSet.contains(i)) continue;\n\n      // Check if adding the current number exceeds maxSum\n      if (sum + i > maxSum) break;\n\n      sum += i;\n      count++;\n    }\n\n    return count;\n  }\n}\n```\n\n\n```python []\nclass Solution:\n    def maxCount(self, banned, n, maxSum):\n        banned_set = set(banned)  # Use a set for efficient lookups\n        total_sum, count = 0, 0\n\n        for i in range(1, n + 1):\n            if i in banned_set:  # Skip banned numbers\n                continue\n            if total_sum + i > maxSum:  # Stop if maxSum is exceeded\n                break\n            total_sum += i\n            count += 1\n\n        return count\n```\n\n\n```javascript []\nvar maxCount = function(banned, n, maxSum) {\n    const bannedSet = new Set(banned); // Use a set for efficient lookups\n    let sum = 0, count = 0;\n\n    for (let i = 1; i <= n; i++) {\n        if (bannedSet.has(i)) continue; // Skip banned numbers\n        if (sum + i > maxSum) break; // Stop if maxSum is exceeded\n        sum += i;\n        count++;\n    }\n\n    return count;\n};\n```\n\n\n```java []\nimport java.util.HashSet;\nimport java.util.Set;\n\nclass Solution {\n    public int maxCount(int[] banned, int n, int maxSum) {\n        Set<Integer> bannedSet = new HashSet<>();\n        for (int num : banned) bannedSet.add(num);\n\n        int sum = 0, count = 0;\n        for (int i = 1; i <= n; i++) {\n            if (bannedSet.contains(i)) continue; // Skip banned numbers\n            if (sum + i > maxSum) break; // Stop if maxSum is exceeded\n            sum += i;\n            count++;\n        }\n\n        return count;\n    }\n}\n```\n\n\n```cpp []\n#include <unordered_set>\n#include <vector>\nusing namespace std;\n\nclass Solution {\npublic:\n    int maxCount(vector<int>& banned, int n, int maxSum) {\n        unordered_set<int> bannedSet(banned.begin(), banned.end());\n        int sum = 0, count = 0;\n\n        for (int i = 1; i <= n; i++) {\n            if (bannedSet.count(i)) continue; // Skip banned numbers\n            if (sum + i > maxSum) break; // Stop if maxSum is exceeded\n            sum += i;\n            count++;\n        }\n\n        return count;\n    }\n};\n```\n\n\n```go []\nfunc maxCount(banned []int, n int, maxSum int) int {\n    bannedSet := make(map[int]bool)\n    for _, num := range banned {\n        bannedSet[num] = true\n    }\n\n    sum, count := 0, 0\n    for i := 1; i <= n; i++ {\n        if bannedSet[i] { // Skip banned numbers\n            continue\n        }\n        if sum+i > maxSum { // Stop if maxSum is exceeded\n            break\n        }\n        sum += i\n        count++\n    }\n\n    return count\n}\n```\n---\n\n![image.png](https://assets.leetcode.com/users/images/d81a7cee-fa73-41a2-82dc-65bf475d960c_1722267693.3902693.png) {:style=\'width:250px\'}
['Array', 'Greedy', 'C', 'Sorting', 'C++', 'Java', 'Go', 'Python3', 'JavaScript', 'Dart']