🔥Max Non-Banned Numbers with Binary Search 🌿 | Simple Java , C++ , python , solutions 🔥
Intuition \u2728\n-     Binary Search for banned:\n    Use a binary search to quickly check if a number is in the banned list.\n-     Iterate from 1 to n:\n   A
# Intuition \u2728\n-     Binary Search for banned:\n    Use a binary search to quickly check if a number is in the banned list.\n-     Iterate from 1 to n:\n   Add non-banned numbers to the sum until it exceeds maxSum.\n-     Stop Early:\n     Break the loop as soon as adding the next number exceeds maxSum.\n\n\n---\n\n\n\n# Approach \uD83D\uDEE0\uFE0F\n-     Sort the banned list to enable binary search.\n-     For each number from 1 to n:\n-     Skip it if it\'s in banned (via search).\n-     Add it to the running sum if within maxSum.\n-     Stop if adding the number exceeds maxSum.\n\n# Complexity\n- Time complexity:\n-     O(klogk+nlogk). k--> sizeof banned array , n --> number range.\n\n- Space complexity:\n-     O(1)\n\n# Code\n```cpp []\nclass Solution {\nprivate:\n    bool search(vector<int>& nums, int target) {\n        int start = 0, end = nums.size()-1;\n        int mid = start + (end-start)/2;\n\n        while(start <= end) {\n            if(nums[mid] == target) return true;\n            else if(nums[mid] > target) {\n                end = mid-1;\n            } else {\n                start = mid + 1;\n            }\n            mid = start + (end-start)/2;\n        }\n        return false;\n    }\npublic:\n    int maxCount(vector<int>& banned, int n, int maxSum) {\n        sort(banned.begin(), banned.end());\n        int cnt = 0;\n        long long unsigned sum = 0;\n\n        for(int val = 1; val <= n; val ++) {\n            if(!search(banned, val)) {\n                sum += val;\n                if(sum <= maxSum) {\n                    cnt++;\n                } else {\n                    return cnt;\n                }\n            }\n        }\n        return cnt;\n    }\n};\n```\n```Java []\nimport java.util.*;\n\nclass Solution {\n    private boolean search(List<Integer> nums, int target) {\n        int start = 0, end = nums.size() - 1;\n        while (start <= end) {\n            int mid = start + (end - start) / 2;\n            if (nums.get(mid) == target) return true;\n            else if (nums.get(mid) > target) end = mid - 1;\n            else start = mid + 1;\n        }\n        return false;\n    }\n\n    public int maxCount(List<Integer> banned, int n, int maxSum) {\n        Collections.sort(banned);\n        int cnt = 0;\n        long sum = 0;\n\n        for (int val = 1; val <= n; val++) {\n            if (!search(banned, val)) {\n                sum += val;\n                if (sum <= maxSum) cnt++;\n                else return cnt;\n            }\n        }\n        return cnt;\n    }\n}\n\n```\n```python []\nclass Solution:\n    def search(self, nums, target):\n        start, end = 0, len(nums) - 1\n        while start <= end:\n            mid = start + (end - start) // 2\n            if nums[mid] == target:\n                return True\n            elif nums[mid] > target:\n                end = mid - 1\n            else:\n                start = mid + 1\n        return False\n\n    def maxCount(self, banned, n, maxSum):\n        banned.sort()\n        cnt = 0\n        total = 0\n\n        for val in range(1, n + 1):\n            if not self.search(banned, val):\n                total += val\n                if total <= maxSum:\n                    cnt += 1\n                else:\n                    return cnt\n        return cnt\n\n```\n```JavaScript []\nclass Solution {\n    search(nums, target) {\n        let start = 0, end = nums.length - 1;\n        while (start <= end) {\n            let mid = Math.floor(start + (end - start) / 2);\n            if (nums[mid] === target) return true;\n            else if (nums[mid] > target) end = mid - 1;\n            else start = mid + 1;\n        }\n        return false;\n    }\n\n    maxCount(banned, n, maxSum) {\n        banned.sort((a, b) => a - b);\n        let cnt = 0, sum = 0;\n\n        for (let val = 1; val <= n; val++) {\n            if (!this.search(banned, val)) {\n                sum += val;\n                if (sum <= maxSum) cnt++;\n                else return cnt;\n            }\n        }\n        return cnt;\n    }\n}\n\n```\n```ruby []\nclass Solution\n    def search(nums, target)\n        start, end_idx = 0, nums.size - 1\n        while start <= end_idx\n            mid = start + (end_idx - start) / 2\n            return true if nums[mid] == target\n            if nums[mid] > target\n                end_idx = mid - 1\n            else\n                start = mid + 1\n            end\n        end\n        false\n    end\n\n    def maxCount(banned, n, maxSum)\n        banned.sort!\n        cnt = 0\n        sum = 0\n\n        (1..n).each do |val|\n            unless search(banned, val)\n                sum += val\n                if sum <= maxSum\n                    cnt += 1\n                else\n                    return cnt\n                end\n            end\n        end\n        cnt\n    end\nend\n\n```\n
['Array', 'Binary Search', 'Greedy', 'Sorting', 'Python', 'C++', 'Java', 'Ruby', 'JavaScript']