EASY TO MEDIUM TO HARD SOLUTION | 2554. Maximum Number of Integers to Choose From a Range I
Intuition\nThe problem requires counting how many integers from 1 to n can be included in a sum without exceeding maxSum, while avoiding any integers that are p
# Intuition\nThe problem requires counting how many integers from 1 to n can be included in a sum without exceeding maxSum, while avoiding any integers that are present in the banned list. The goal is to maximize this count.\n\n**Key Observations:**\n1. **Banned Integers**: We need to skip any integers that are in the banned list.\n2. **Sum Constraint:** We have to ensure that the cumulative sum of the selected integers does not exceed maxSum.\n3. **Early Stopping:** If adding a number exceeds maxSum, we can stop checking further numbers since all subsequent numbers will be larger and will also exceed maxSum.\n\n# Approach\n1. Use a Hash Map for Banned Integers: We utilize an unordered map (or set) to quickly check if an integer is banned.\n2. Iterate Through Possible Integers: Loop through integers from 1 to n.\n3. Check for Banned Status: For each integer, check if it is not banned.\n4. Update Sum and Count:\n-  If it\u2019s not banned, add it to the cumulative sum.\n-  If adding this integer keeps the sum within maxSum, increment the count.\n-  If adding it exceeds maxSum, break out of the loop since further additions will only increase the sum.\n5. Return Count: Finally, return the count of integers that can be included without exceeding maxSum.\n\n# Complexity\n- **Time complexity:**\n1. Constructing the hash map takes O(b) time, where b is the number of banned integers.\n2. The loop runs at most O(n) times (for each integer from 1 to n).\n3. Overall, the time complexity is O(b + n).\n\n- **Space complexity:**\n1. The space used by the hash map is O(b), where b is the number of banned integers.\n2. Thus, the space complexity is O(b).\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int maxCount(vector<int>& banned, int n, int maxSum) {\n        unordered_map<int, int> mp;\n        for (int i : banned) {\n            mp[i]++;\n        }\n\n        int sum = 0, res = 0;\n        for (int i = 1; i <= n; i++) {\n            if (!mp[i]) { // If not banned\n                sum += i;\n                if (sum <= maxSum) {\n                    res++;\n                } else {\n                    return res; // Stop as remaining values will also exceed maxSum\n                }\n            }\n        }\n        return res;\n    }\n};\n```
['Array', 'Hash Table', 'Binary Search', 'Greedy', 'Sorting', 'C++']