O(N) solution : Without using DP
Intuition\nIt\'s not mentioned in que whether "banned" array contains any repeated number or not, so to be on safer side I used map for it. Also for checking pr
# Intuition\nIt\'s not mentioned in que whether "banned" array contains any repeated number or not, so to be on safer side I used map for it. Also for checking presence in banned array, it takes lesser time.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nFor every number from 1-n, I checked whether it\'s present in banned array or not using map as it comparatively lesser time (i.e, logN).\nIf it\'s not present and sum do not exceed maxSum, I updated count and sum.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(NlogN)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ --> O(M)\n\n# Code\n```\nclass Solution {\npublic:\n    int maxCount(vector<int>& banned, int n, int maxSum) {\n         //in the que it is not mentioned that "banned" array contains distinct elements or not so I made a map for it\n        map<int, int> mp; \n        int sum = 0;\n        int count = 0;\n        \n        for(auto it : banned) mp[it]++;\n        \n        for(int i=1; i<=n; i++){\n            //for every int from 1-n we\'ll check whether it is in banned array or not & it\'s sum less than maxSum or not\n            if((mp.find(i) == mp.end()) && sum+i <= maxSum){\n                sum += i;\n                count++;\n            }\n        }\n        return count;\n    }\n};\n```
['C++']