✅Easiest (C++/Java/Python) Solution With Detailed Explanation✅
Intuition\nThe function maxCount aims to calculate the maximum count of distinct numbers from 1 to n that can be added together without exceeding a given maxSum
# Intuition\nThe function `maxCount` aims to calculate the maximum count of distinct numbers from 1 to `n` that can be added together without exceeding a given `maxSum`, while also ensuring that none of these numbers are in a provided `banned` list. Here\'s a detailed breakdown of the approach:\n\n# Approach\n\n\n1. **Use a Hash Map for Banned Numbers**: The function starts by creating a hash map (or unordered_map in C++) to store the banned numbers for quick lookup. This step ensures that we can efficiently check if a number is banned or not.\n\n2. **Initialize Variables**: It initializes variables `res` to store the count of numbers included, `sum` to keep track of the current sum of included numbers, and `i` to iterate through numbers from 1 to `n`.\n\n3. **Iterate through Numbers**: The function then iterates over numbers from 1 to `n`. For each number `i`, it checks two conditions:\n   - **Is the Number Not Banned**: The function checks if the current number `i` is not in the banned list (using the hash map). If `i` is banned, it is skipped.\n   - **Does Adding the Number Exceed `maxSum`**: It checks whether adding the current number to the sum would exceed `maxSum`. If it would, the loop breaks as adding any further numbers would only increase the sum.\n\n4. **Update Count and Sum**: If both conditions are met, the function increments the count (`res`) and adds the number to the sum (`sum`).\n\n5. **Return Result**: After the loop, the function returns the count `res`, which represents the maximum count of distinct numbers that can be added without exceeding `maxSum` and not including any banned numbers.\n\nThis approach is efficient as it avoids unnecessary checks or iterations and uses a hash map for quick lookups. The early break from the loop when `sum + i > maxSum` is encountered ensures that the function does not perform redundant calculations.\n\n# Complexity\n\n1. **Time Complexity**: The primary factor in the time complexity is the loop that iterates from 1 to `n`. In the worst case, this loop runs for all `n` numbers (if none of them are banned and if the `maxSum` is sufficiently large to include all numbers). Therefore, the time complexity is \\(O(n)\\), where \\(n\\) is the upper limit of the range of numbers.\n\n2. **Space Complexity**: The space complexity is determined by the additional space used by the hash map storing the banned numbers. In the worst case, the hash map could store all elements in the `banned` array, which has a size that is independent of `n`. Therefore, the space complexity is \\(O(m)\\), where \\(m\\) is the size of the `banned` array. \n\n# Code\n```C++ []\nclass Solution {\npublic:\n    int maxCount(vector<int>& banned, int n, int maxSum) {\n        unordered_map<int, int> M;\n        for (auto num : banned)\n            M[num]++;\n\n        int res = 0;\n        int sum = 0;\n        int i=1;\n        while (i<=n)\n        {\n            if (M.find(i) == M.end())\n            {\n                if (sum+i <= maxSum)\n                {\n                    res++;\n                    sum += i;\n                }\n                else\n                    break;\n            }\n            i++;\n        }\n\n        return res;\n    }\n};\n```\n```Java []\npublic class Solution {\n    public int maxCount(int[] banned, int n, int maxSum) {\n        Set<Integer> bannedSet = new HashSet<>();\n        for (int num : banned) {\n            bannedSet.add(num);\n        }\n\n        int res = 0;\n        int sum = 0;\n        int i = 1;\n        while (i <= n) {\n            if (!bannedSet.contains(i)) {\n                if (sum + i <= maxSum) {\n                    res++;\n                    sum += i;\n                } else {\n                    break;\n                }\n            }\n            i++;\n        }\n\n        return res;\n    }\n}\n\n```\n```Python []\nclass Solution:\n    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n        banned_set = set(banned)\n        res = 0\n        sum = 0\n        i = 1\n        while i <= n:\n            if i not in banned_set:\n                if sum + i <= maxSum:\n                    res += 1\n                    sum += i\n                else:\n                    break\n            i += 1\n\n        return res\n\n```
['Hash Table', 'Python', 'C++', 'Java']