🔥🚀 Ultimate Solution | 💯 Beats 100% | 🔍 Binary Search + 🧹 Sorting + 💡 Greedy 🏆
\uD83E\uDDE0 Intuition\nWe want to select as many numbers from 1 to n without exceeding a maxSum, ensuring no number is in the banned list. We\'ll use sorting a
# \uD83E\uDDE0 Intuition\nWe want to select as many numbers from 1 to n without exceeding a maxSum, ensuring no number is in the banned list. We\'ll use sorting and binary search for efficiency. \uD83D\uDD0D\n\n---\n\n# \uD83D\uDD04 Approach\n1. Sort the Banned List: Helps us perform a fast binary search. \u26A1\n2. Binary Search: For each number i from 1 to n, check if it\'s in banned. If not, add it to the sum. \uD83D\uDCCA\n3. Sum Check: Stop adding numbers once the sum exceeds maxSum. \uD83D\uDEAB\uD83D\uDCB0\n4. Early Termination: Exit as soon as the sum exceeds maxSum to save time. \u23F1\uFE0F\n\n---\n\n# Complexity\n## \u23F1\uFE0F Time Complexity\n- Sorting banned: O(m log m) (where m is size of banned) \uD83D\uDCCF\n- Binary Search for each number from 1 to n: *O(n log m)* \uD83D\uDD0D\n\n## \uD83D\uDCBE Space Complexity\n- Space for banned list: *O(m)* \uD83D\uDDC2\uFE0F\n\n---\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    bool binary_search(vector<int>& arr , int target)\n    {\n        int n = arr.size();\n        int start = 0 , end = n-1 ;\n        int mid = start + (end - start)/2 ;\n\n        while(start <= end)\n        {\n            if(arr[mid] == target)\n            {\n                return true ;\n            }\n            else if(arr[mid] > target)\n            {\n                end = mid -1 ;\n            }\n            else{\n                start = mid + 1 ;\n            }\n            mid = start + (end - start) /2 ;\n\n        }\n        return false ;\n    }\n    int maxCount(vector<int>& banned, int n, int maxSum) {\n        int cnt = 0 ;\n        long long unsigned sum = 0 ;\n        sort(banned.begin(), banned.end()) ;\n\n        for(int i = 1 ; i <= n ; i++)\n        {\n            if( !binary_search(banned , i))\n            {\n                sum += i ;\n                if(sum <= maxSum)\n                {\n                    cnt++ ;\n                }\n                else\n                {\n                    return cnt ;\n                }\n            }\n        }\n        return cnt ;\n        \n    }\n};\n```\n\n```java []\nimport java.util.Arrays;\n\nclass Solution {\n    public boolean binarySearch(int[] arr, int target) {\n        int n = arr.length;\n        int start = 0, end = n - 1;\n        int mid = start + (end - start) / 2;\n\n        while (start <= end) {\n            if (arr[mid] == target) {\n                return true;\n            } else if (arr[mid] > target) {\n                end = mid - 1;\n            } else {\n                start = mid + 1;\n            }\n            mid = start + (end - start) / 2;\n        }\n        return false;\n    }\n\n    public int maxCount(int[] banned, int n, int maxSum) {\n        int cnt = 0;\n        long sum = 0;\n        Arrays.sort(banned);\n\n        for (int i = 1; i <= n; i++) {\n            if (!binarySearch(banned, i)) {\n                sum += i;\n                if (sum <= maxSum) {\n                    cnt++;\n                } else {\n                    return cnt;\n                }\n            }\n        }\n        return cnt;\n    }\n}\n\n\n```\n```javascript []\nclass Solution {\n    binarySearch(arr, target) {\n        let n = arr.length;\n        let start = 0, end = n - 1;\n        let mid = Math.floor(start + (end - start) / 2);\n\n        while (start <= end) {\n            if (arr[mid] === target) {\n                return true;\n            } else if (arr[mid] > target) {\n                end = mid - 1;\n            } else {\n                start = mid + 1;\n            }\n            mid = Math.floor(start + (end - start) / 2);\n        }\n        return false;\n    }\n\n    maxCount(banned, n, maxSum) {\n        let cnt = 0;\n        let sum = 0;\n        banned.sort((a, b) => a - b);\n\n        for (let i = 1; i <= n; i++) {\n            if (!this.binarySearch(banned, i)) {\n                sum += i;\n                if (sum <= maxSum) {\n                    cnt++;\n                } else {\n                    return cnt;\n                }\n            }\n        }\n        return cnt;\n    }\n}\n\n\n```\n```python []\nclass Solution:\n    def binary_search(self, arr, target):\n        n = len(arr)\n        start, end = 0, n - 1\n\n        while start <= end:\n            mid = start + (end - start) // 2\n            if arr[mid] == target:\n                return True\n            elif arr[mid] > target:\n                end = mid - 1\n            else:\n                start = mid + 1\n\n        return False\n\n    def maxCount(self, banned, n, maxSum):\n        cnt = 0\n        sum_ = 0\n        banned.sort()\n\n        for i in range(1, n + 1):\n            if not self.binary_search(banned, i):\n                sum_ += i\n                if sum_ <= maxSum:\n                    cnt += 1\n                else:\n                    return cnt\n        return cnt\n\n\n```\n```ruby []\nclass Solution\n  def binary_search(arr, target)\n    n = arr.size\n    start = 0\n    end_index = n - 1\n\n    while start <= end_index\n      mid = start + (end_index - start) / 2\n\n      if arr[mid] == target\n        return true\n      elsif arr[mid] > target\n        end_index = mid - 1\n      else\n        start = mid + 1\n      end\n\n    end\n    false\n  end\n\n  def max_count(banned, n, max_sum)\n    cnt = 0\n    sum = 0\n    banned.sort!\n\n    (1..n).each do |i|\n      unless binary_search(banned, i)\n        sum += i\n        if sum <= max_sum\n          cnt += 1\n        else\n          return cnt\n        end\n      end\n    end\n    cnt\n  end\nend\n\n\n```\n```go []\npackage main\n\nimport (\n\t"sort"\n)\n\ntype Solution struct{}\n\nfunc (s *Solution) binarySearch(arr []int, target int) bool {\n\tn := len(arr)\n\tstart, end := 0, n-1\n\n\tfor start <= end {\n\t\tmid := start + (end-start)/2\n\t\tif arr[mid] == target {\n\t\t\treturn true\n\t\t} else if arr[mid] > target {\n\t\t\tend = mid - 1\n\t\t} else {\n\t\t\tstart = mid + 1\n\t\t}\n\t}\n\treturn false\n}\n\nfunc (s *Solution) maxCount(banned []int, n int, maxSum int) int {\n\tcnt := 0\n\tsum := 0\n\tsort.Ints(banned)\n\n\tfor i := 1; i <= n; i++ {\n\t\tif !s.binarySearch(banned, i) {\n\t\t\tsum += i\n\t\t\tif sum <= maxSum {\n\t\t\t\tcnt++\n\t\t\t} else {\n\t\t\t\treturn cnt\n\t\t\t}\n\t\t}\n\t}\n\treturn cnt\n}\n\n\n``` \n```rust []\nuse std::cmp::Ordering;\n\nstruct Solution;\n\nimpl Solution {\n    fn binary_search(arr: &Vec<i32>, target: i32) -> bool {\n        let mut start = 0;\n        let mut end = arr.len() as i32 - 1;\n\n        while start <= end {\n            let mid = start + (end - start) / 2;\n            match arr[mid as usize].cmp(&target) {\n                Ordering::Equal => return true,\n                Ordering::Greater => end = mid - 1,\n                Ordering::Less => start = mid + 1,\n            }\n        }\n        false\n    }\n\n    pub fn max_count(banned: Vec<i32>, n: i32, max_sum: i32) -> i32 {\n        let mut cnt = 0;\n        let mut sum: u64 = 0;\n        let mut banned = banned;\n        banned.sort_unstable();\n\n        for i in 1..=n {\n            if !Self::binary_search(&banned, i) {\n                sum += i as u64;\n                if sum <= max_sum as u64 {\n                    cnt += 1;\n                } else {\n                    return cnt;\n                }\n            }\n        }\n        cnt\n    }\n}\n\n\n```\n```c# []\nusing System;\nusing System.Collections.Generic;\nusing System.Linq;\n\npublic class Solution \n{\n    private bool BinarySearch(List<int> arr, int target)\n    {\n        int n = arr.Count;\n        int start = 0, end = n - 1;\n        int mid = start + (end - start) / 2;\n\n        while (start <= end)\n        {\n            if (arr[mid] == target)\n            {\n                return true;\n            }\n            else if (arr[mid] > target)\n            {\n                end = mid - 1;\n            }\n            else\n            {\n                start = mid + 1;\n            }\n            mid = start + (end - start) / 2;\n        }\n        return false;\n    }\n\n    public int MaxCount(IList<int> banned, int n, int maxSum) \n    {\n        int cnt = 0;\n        long sum = 0;\n        List<int> sortedBanned = banned.OrderBy(x => x).ToList();\n\n        for (int i = 1; i <= n; i++)\n        {\n            if (!BinarySearch(sortedBanned, i))\n            {\n                sum += i;\n                if (sum <= maxSum)\n                {\n                    cnt++;\n                }\n                else\n                {\n                    return cnt;\n                }\n            }\n        }\n        return cnt;\n    }\n}\n\n\n```\n
['Binary Search', 'Sorting', 'Python', 'C++', 'Java', 'Go', 'Rust', 'Ruby', 'JavaScript', 'C#']