🐱‍👓Simple and easy to understandable approach ✨ || Full Explanation with example
Intuition\n Describe your first thoughts on how to solve this problem. \n\nOur basic intituion is, if we have to reach to y from x (knowing x <= y) considering 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nOur basic intituion is, if we have to reach to `y` from `x` (knowing x <= y) considering doing one operation at a time. Then, total operation will be `y-x`. and from `x` and `z` to `y` (knowing x, z <= y), the total operation will be `y-x` and `y-z` and the combined total operation will be `2y - (x + z)`.\n\nFor Example, we have `nums = [1, 2, 3, 4, 5]` and `queries = [4]`.\nSo, we reach to 4 from 1 in 3 steps, from 2 in 2 steps, from 3 in 1 steps, from 4 in 0 steps and from 5 in 1 steps.\n\nTherefore, total operations will be 7.\n\n\nNow to reach to 4 from 1, 2, 3 the combined total operation will be `3 * 4 - (1 + 2 + 3) = 6` and from 4 and 5 combined total operation is `(4 + 5) - 2 * 4 = 1`\n\nThe formula is `n x target - (sum of all elements)` if all elements are less than equal to target. and `(sum of all elements) - n x target` if all elements greater than equal to target, where _n_ is no of elements\n\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nSort the `nums` array. And find the [`prefixSum`](https://leetcode.com/problems/running-sum-of-1d-array/description/) for the sorted `nums` array.\n\nNow iterate over the `queries` list. and find the optimal position for each query in sorted `nums` list (say `idx`) using binary search.\n\nif `idx == n` or `idx == 0`: add `abs(query * n - prefixSum[n-1])` to your `ans` array.\nelse: calculate the total operation for the left side of `idx` _i.e.,_ `abs(prefixSum[idx-1] - query * idx)` and total operation for the right side (from `idx` to `n-1`) _i.e.,_ `abs(query * (n-idx) - (prefixSum[n-1] - prefixSum[idx-1]))`, add them and append them in your `ans` array.\n\nNow `return ans`\n \n# Complexity\n- Time complexity: $O(n + (m+n) log(n))$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $O(n)$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n\n        nums.sort()\n        n = len(nums)\n\n        prefixSum = []\n        for num in nums:\n            if not prefixSum:\n                prefixSum.append(num)\n                continue\n            last = prefixSum[-1]\n            prefixSum.append(num + last)\n\n        ans = []\n        for query in queries:\n            tmp = 0\n\n            idx = self.positionInSortedArray(nums, query)\n            if idx == n or idx == 0:\n                tmp += abs(query * n - prefixSum[n - 1])\n            elif 0 < idx < n:\n                temp = query * (n-idx)\n                # left\n                tmp += abs(query * idx - prefixSum[idx - 1])\n                # right\n                tmp += abs(query * (n - idx) - (prefixSum[n - 1] - prefixSum[idx - 1]))\n\n            ans.append(tmp)\n\n        return ans\n\n    def positionInSortedArray(self, arr: List[int], k: int) -> int:\n\n        low, high = 0, len(arr)\n\n        while low < high:\n\n            mid = (low + high) // 2\n            if arr[mid] == k:\n                return mid\n            elif arr[mid] > k:\n                high = mid\n            else:\n                low = mid + 1\n\n        return (low + high) // 2\n```
['Array', 'Binary Search', 'Sorting', 'Prefix Sum', 'Python3']