[C++, Java, Python3] Prefix Sums + Binary Search
Intuition\n If there are j numbers in nums that are smaller than query[i], you need to find query[i] * j - sum(j numbers smaller than query[i]) to find incremen
# Intuition\n* If there are `j` numbers in `nums` that are smaller than `query[i]`, you need to find `query[i] * j - sum(j numbers smaller than query[i])` to find increments required in `nums`\n* If there are `k` numbers in `nums` that are greater than `query[i]`, you need to find `sum(k numbers larger than query[i]) - query[i] * k` to find decrements required in `nums`\n* Sum of above two values is `ans[i]`\n![Screen Shot 2023-03-26 at 12.05.05 PM.png](https://assets.leetcode.com/users/images/a0061bf7-ab30-41dc-be3c-0b0bf2872469_1679857679.0441012.png)\n\n\n# Approach\n* To find smaller numbers than `query[i]` we can sort the array and use binary search\n* Binary search over sorted `nums` to find index of `query[i]`\n* Then use prefix sums to find sum of number in smaller and larger segments\n* `prefix[n] - prefix[i]` is sum of numbers greater than or equal to `query[i]`\n* `prefix[i]` is sum of numbers smaller than `query[i]`\n* `query[i] * i - prefix[i]` is increments required\n*  `prefix[n] - prefix[i] - query[i] * (n - i)` is decrements required\n* Total = `query[i] * i - prefix[i] + prefix[n] - prefix[i] - query[i] * (n - i)`\n* Can be simplified to `query[i] * (2 * i - n) + prefix[n] - 2 * prefix[i]`\n\n# Complexity\n- Time complexity: `O((n + m) * log(n))`\n\n- Space complexity: `O(n)`\n\n# Code\n**Python3**:\n```\ndef minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n    nums.sort()\n    ans, n, prefix = [], len(nums), [0] + list(accumulate(nums))\n    for x in queries:\n        i = bisect_left(nums, x)\n        ans.append(x * (2 * i - n) + prefix[n] - 2 * prefix[i])\n    return ans\n```\n```\ndef minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n    nums.sort()\n    prefix = [0] + list(accumulate(nums))\n    for x in queries:\n        i = bisect_left(nums, x)\n        yield x * (2 * i - len(nums)) + prefix[-1] - 2 * prefix[i]\n```\n**C++**:\n```\nvector<long long> minOperations(vector<int>& nums, vector<int>& queries) {\n    sort(nums.begin(), nums.end());\n    int n = nums.size();\n    vector<long long> ans, prefix(n + 1);\n    for (int i = 0; i < n; i++)\n        prefix[i + 1] = prefix[i] + (long long) nums[i];\n    for (int& x : queries) {\n        int i = lower_bound(nums.begin(), nums.end(), x) - nums.begin();\n        ans.push_back(1LL * x * (2 * i - n) + prefix[n] - 2 * prefix[i]);\n    }\n    return ans;\n}\n```\n\n**Java**:\n```\npublic List<Long> minOperations(int[] nums, int[] queries) {\n    Arrays.sort(nums);\n    List<Long> ans = new ArrayList<>();\n    int n = nums.length;\n    long[] prefix = new long[n + 1];\n    for (int i = 1; i <= n; i++)\n        prefix[i] = prefix[i - 1] + nums[i - 1];\n    for (int x: queries) {\n        int i = bisect_left(nums, x);\n        ans.add(1L * x * (2 * i - n) + prefix[n] - 2 * prefix[i]);\n    }\n    return ans;\n}\nprivate int bisect_left(int[] nums, int x) {\n    int lo = 0, hi = nums.length;\n    while (lo < hi) {\n        int mid = lo + (hi - lo) / 2;\n        if (nums[mid] < x) lo = mid + 1;\n        else hi = mid;\n    }\n    return lo;\n}\n```\n\n**Java using Arrays.binarySearch**:\n```\npublic List<Long> minOperations(int[] nums, int[] queries) {\n    Arrays.sort(nums);\n    List<Long> ans = new ArrayList<>();\n    int n = nums.length;\n    long[] prefix = new long[n + 1];\n    for (int i = 1; i <= n; i++)\n        prefix[i] = prefix[i - 1] + nums[i - 1];\n    for (int x: queries) {\n        int i = Arrays.binarySearch(nums, x);\n        if (i < 0) i = -(i + 1); // convert negative index to insertion point\n        ans.add(1L * x * (2 * i - n) + prefix[n] - 2 * prefix[i]);\n    }\n    return ans;\n}\n```\n*Good to know*: In Java, Arrays.binarySearch returns a negative index when the target element is not found in the array. The negative index returned is equal to -(insertion point) - 1, where the insertion point is the index at which the target element would be inserted into the array to maintain the sorted order.\n\nFor example, suppose we have an array arr = {1, 3, 5, 7, 9} and we want to search for the element 4. The Arrays.binarySearch(arr, 4) method would return -3. To convert this to the insertion point, we take the absolute value of the negative index and subtract 1: insertion point = |-(-3)| - 1 = 2.\n\nTherefore, the insertion point for the element 4 in the sorted array arr would be at index 2, which is the position where we would need to insert 4 to maintain the sorted order.\n\n**More binary search problems:**\n[Minimum Time to Repair Cars](https://leetcode.com/problems/minimum-time-to-repair-cars/solutions/3311975/c-java-python3-binary-search-1-liner/)\n[Minimum Time to Complete Trips](https://leetcode.com/problems/minimum-time-to-complete-trips/solutions/1802415/python3-java-c-binary-search-1-liner/)\n[Kth Missing Positive Number](https://leetcode.com/problems/kth-missing-positive-number/solutions/3262163/c-java-python3-1-line-ologn/)\n[Maximum Tastiness of Candy Basket](https://leetcode.com/problems/maximum-tastiness-of-candy-basket/solutions/2947983/c-java-python-binary-search-and-sorting/)\n[Number of Flowers in Full Bloom](https://leetcode.com/problems/number-of-flowers-in-full-bloom/solutions/1976804/python3-2-lines-sort-and-binary-search/)
['C++', 'Java', 'Python3']