🔥Beats 100 % 🔥 | 4 MS | ✔️ Boolean Map & HashMap ✔️ | 2 Solutions |
\n\n---\n# Solution 1 : Optimized (Boolean Map)\n---\n\n# Intuition\nThis solution uses a boolean array map instead of a HashMap to track banned numbers. Since 
![image.png](https://assets.leetcode.com/users/images/c68c2872-038a-4216-a053-8f98d92bd303_1733450839.8773375.png)\n\n---\n# Solution 1 : Optimized (Boolean Map)\n---\n\n# Intuition\nThis solution uses a **boolean** array `map` instead of a `HashMap` to track **banned numbers**. Since the constraints suggest the values in banned are within a limited range **1 to 10,000**, a `boolean` array is more memory-efficient and allows `O(1)` lookups. By iterating through numbers from `1 to n`, we check:If the current number is banned. If adding the current number to the sum exceeds `maxSum`.\n\n# Approach\n`Step 1` **Create a Boolean Array for Banned Numbers :**\n- Use a `boolean[]` map of size `10001` & mark banned **true** for banned.\n\n`Step 2` **Initialize Variables :**\n- Use `sum` to track the total `sum` of selected numbers.\n- Use `count` to count the **selected numbers**.\n\n`Step 1` **Iterate Over Numbers :**\n- For each number `i` from `1 to n` :\n    - If adding `i` to `sum` exceeds `maxSum`, stop the **loop**.\n    - If `i` is not banned `map[i] == false`, include it in the `sum` and increment `count`.\n\n`Step 1` **Return the Count :**\n- After the loop, return the value of `count`.\n\n# Complexity\n- Time complexity : $$O(n)$$\n- Space complexity : $$O(1)$$\n\n# Code\n```java []\nclass Solution\n{\n    public int maxCount(int[] banned, int n, int maxSum)\n    {\n        // Step 1: Create a boolean array to mark banned numbers\n        boolean[] map = new boolean[10001];\n        for (int i = 0; i < banned.length; i++)\n        {\n            map[banned[i]] = true; // Mark the banned numbers as true\n        }\n\n        // Step 2: Initialize variables for sum and count\n        int sum = 0;    // To store the current sum of selected numbers\n        int count = 0;  // To count the number of integers added\n\n        // Step 3: Iterate over numbers from 1 to n\n        for (int i = 1; i <= n; i++)\n        {\n            // Step 4: Check if adding this number exceeds maxSum\n            if (sum + i > maxSum)\n            {\n                break; // Stop further iteration if sum exceeds maxSum\n            }\n\n            // Step 5: Include the number if it\'s not banned\n            if (!map[i])\n            {\n                sum += i;   // Add the current number to the sum\n                count++;   // Increment the count of selected numbers\n            }\n        }\n\n        // Step 6: Return the total count of selected numbers\n        return count;\n    }\n}\n\n```\n\n---\n# Solution 2 : Brute Force (HashMap)\n---\n\n# Intuition\nThe problem is about selecting integers from `1 to n` such that their **sum** does not exceed ``maxSum`` and the integers should not be in the **banned** list. By using a `HashMap`, we can efficiently check if a number is **banned**. We iterate through the numbers, include them in the `sum` if they are not banned and the total sum does not exceed `maxSum`.\n\n# Approach\n`Step 1` **Create a HashMap to Store Banned Numbers :**\n- Add all the **banned numbers** to the `map` for quick lookup.\n\n`Step 2` **Initialize Variables :**\n- Use `sum` to track the current `total sum`.\n- Use `count` to track the number of integers added to the `sum`.\n\n`Step 3` **Iterate Over Numbers :**\n- For every number `i` from `1 to n`:\n    - Check if it is not in the banned list `HashMap`.\n    - If adding `i to sum` does not exceed `maxSum`, include it in the `sum` and **increment count**.\n\n`Step 4` **Return the Count :**\n- After the loop, return the value of `count`.\n\n# Complexity\n- Time complexity : $$O(banned.length + n)$$\n- Space complexity : $$O(n)$$\n\n# Code\n```java []\nclass Solution\n{\n    public int maxCount(int[] banned, int n, int maxSum)\n    {\n        // Step 1: Create a HashMap to store banned numbers\n        HashMap<Integer, Integer> map = new HashMap<>();\n        for (int i = 0; i < banned.length; i++)\n        {\n            map.put(banned[i], map.getOrDefault(banned[i], 0) + 1);\n        }\n\n        // Step 2: Initialize sum and count\n        int sum = 0;    // To store the current sum of selected numbers\n        int count = 0;  // To count the number of integers added\n\n        // Step 3: Iterate over numbers from 1 to n\n        for (int i = 1; i <= n; i++)\n        {\n            // Step 4: Check if the current number is not banned\n            if (map.get(i) == null)\n            {\n                // Step 5: Check if adding this number exceeds maxSum\n                if (sum + i <= maxSum)\n                {\n                    sum += i;   // Add the current number to the sum\n                    count++;   // Increment the count of selected numbers\n                }\n            }\n        }\n\n        // Step 6: Return the total count of selected numbers\n        return count;\n    }\n}\n```
['Array', 'Hash Table', 'Binary Search', 'Greedy', 'Ordered Map', 'Sorting', 'Java']