Binary Search Solution to find out special number on every possible outlier
Approach\n\n#### Key Insights:\n1. Sorting the Array:\n   - Sorting simplifies the process of checking for conditions on the numbers.\n   - By sorting, we can i
### Approach\n\n#### Key Insights:\n1. **Sorting the Array**:\n   - Sorting simplifies the process of checking for conditions on the numbers.\n   - By sorting, we can iterate from the largest to the smallest, reducing unnecessary computations.\n\n2. **Two-Pointer Search**:\n   - For each candidate number (potential outlier), perform a binary search on the remaining numbers.\n   - Exclude the candidate number from the search to avoid false positives.\n\n3. **Mathematical Validation**:\n   - Calculate the total sum of the array (`sum`).\n   - If removing a number (`nums[i]`) makes `sum - nums[i]` equal to one of the other numbers in the array, this is the valid outlier.\n\n---\n\n### Implementation\n\nHere\u2019s the code for the solution:\n\n```cpp []\nclass Solution {\n    int check(long long sum, vector<int>& nums, int i) {\n        int n = nums.size();\n        int l = 0, r = n - 1;\n\n        while (l <= r) {\n            int mid = (l + r) / 2;\n            if (mid == i) {\n                if (mid < r) mid++; \n                else if (mid > l) mid--; \n                else return false;\n            }\n\n            if (sum - nums[mid] == nums[mid])\n                return true;\n            if (sum - nums[mid] < nums[mid]) r = mid - 1;\n            else l = mid + 1;\n        }\n        return false;\n    }\n\npublic:\n    int getLargestOutlier(vector<int>& nums) {\n        sort(nums.begin(), nums.end());\n        long long sum = accumulate(nums.begin(), nums.end(), 0);\n        int n = nums.size();\n\n        for (int i = n - 1; i >= 0; i--) {\n            if (check(sum - nums[i], nums, i)) return nums[i];\n        }\n        return -1;\n    }\n};\n```\n\n```python []\nclass Solution:\n    def check(self, total_sum, nums, index):\n        n = len(nums)\n        left, right = 0, n - 1\n\n        while left <= right:\n            mid = (left + right) // 2\n            if mid == index:\n                if mid < right:\n                    mid += 1\n                elif mid > left:\n                    mid -= 1\n                else:\n                    return False\n            \n            if total_sum - nums[mid] == nums[mid]:\n                return True\n            elif total_sum - nums[mid] < nums[mid]:\n                right = mid - 1\n            else:\n                left = mid + 1\n\n        return False\n\n    def getLargestOutlier(self, nums):\n        nums.sort()\n        total_sum = sum(nums)\n        n = len(nums)\n\n        for i in range(n - 1, -1, -1):\n            if self.check(total_sum - nums[i], nums, i):\n                return nums[i]\n\n        return -1\n```\n\n```java []\nimport java.util.*;\n\nclass Solution {\n    private boolean check(long sum, int[] nums, int index) {\n        int n = nums.length;\n        int left = 0, right = n - 1;\n\n        while (left <= right) {\n            int mid = (left + right) / 2;\n            if (mid == index) {\n                if (mid < right) mid++;\n                else if (mid > left) mid--;\n                else return false;\n            }\n\n            if (sum - nums[mid] == nums[mid]) return true;\n            if (sum - nums[mid] < nums[mid]) right = mid - 1;\n            else left = mid + 1;\n        }\n        return false;\n    }\n\n    public int getLargestOutlier(int[] nums) {\n        Arrays.sort(nums);\n        long sum = Arrays.stream(nums).asLongStream().sum();\n\n        for (int i = nums.length - 1; i >= 0; i--) {\n            if (check(sum - nums[i], nums, i)) return nums[i];\n        }\n        return -1;\n    }\n}\n```\n\n```javascript []\nfunction check(totalSum, nums, index) {\n    let left = 0, right = nums.length - 1;\n\n    while (left <= right) {\n        let mid = Math.floor((left + right) / 2);\n        if (mid === index) {\n            if (mid < right) mid++;\n            else if (mid > left) mid--;\n            else return false;\n        }\n\n        if (totalSum - nums[mid] === nums[mid]) return true;\n        if (totalSum - nums[mid] < nums[mid]) right = mid - 1;\n        else left = mid + 1;\n    }\n    return false;\n}\n\nfunction getLargestOutlier(nums) {\n    nums.sort((a, b) => a - b);\n    let totalSum = nums.reduce((a, b) => a + b, 0);\n\n    for (let i = nums.length - 1; i >= 0; i--) {\n        if (check(totalSum - nums[i], nums, i)) return nums[i];\n    }\n    return -1;\n}\n```\n---\n\n\n### Complexity Analysis\n1. **Time Complexity**:\n   - Sorting the array: \\(O(nlog n)\\)\n   - Binary search for each element: \\(O(nlog n)\\)\n   - Total: \\(O(nlog n)\\)\n\n2. **Space Complexity**:\n   - Sorting uses \\(O(1)\\) extra space (in-place sorting with a mutable array).\n\n---\n\n### Example Walkthrough\n\n#### Input:\n```plaintext\nnums = [6, 1, 3, 10, 2]\n```\n\n#### Execution:\n1. **Sort the array**: `[1, 2, 3, 6, 10]`\n2. Calculate `sum = 22`.\n3. Iterate from the largest number (`10`):\n   - Check if removing `10` satisfies the condition. \n   - Result: `10` is the largest outlier.\n\n#### Output:\n```plaintext\n10\n```\n
['Binary Search', 'Python', 'C++', 'Java', 'JavaScript']