Beats 98% || Simple C++ Explanation || Binary Search || Prefix Sum
Intuition\nThe code aims to efficiently find the minimum cost of operations on a sorted array for given queries. The intuition involves traversing the queries v
# Intuition\nThe code aims to efficiently find the minimum cost of operations on a sorted array for given queries. The intuition involves traversing the queries vector once and recognizing the need for a logarithmic time solution. Hence, the idea of using binary search is considered. \n\n# Approach\n In the approach, the array is sorted, and the prefix sum is calculated. For each query, binary search is utilized to find the position of the target value in the array. The cost is then calculated as follows:\n- Count of elements before the target multiplied by the target\n  (target * (count of elements before target) - sum of elements before target)\n- Plus the sum of elements after the target\n  (sum of all elements - sum of elements before target - (count of elements after target) * target)\nThis process is repeated for each query, and the results are stored in a vector. \n\n\n\n# Complexity\n- Time complexity:\nThe time complexity is O(m * log(n)), where m is the number of queries and n is the size of the array, due to the logarithmic binary search operation. \n\n- Space complexity:\nThe space complexity is O(n), where n is the size of the array, mainly due to storing the sorted array and the prefix sum vector. \n\n\n# Code\n```\ntypedef long long ll;\nclass Solution {\npublic:\n    // find cost using binary search and prefix sum in log(n) time complexity\n    ll findCost(vector<int>& nums, vector<ll> &pre, ll target) {\n        ll n = nums.size();\n        ll cost = 0, sum = pre[n-1];\n\n        // edge cases\n        if(target < nums[0])\n            return sum - target*n;\n        if(target > nums[n-1])\n            return target*n - sum;\n        \n        // binary search\n        ll left = 0, right = n-1, i = 0;\n        while(left <= right) {\n            ll mid = (left + right) /2;\n            if(nums[mid] <= target) {\n                i = mid;\n                left = mid + 1;\n            }\n            else\n                right = mid-1;\n        }\n\n        cost = (target * (i + 1) - pre[i]) + (sum - pre[i]) - (n - i - 1) * target;\n\n        return cost;\n    }\n\n    vector<long long> minOperations(vector<int>& nums, vector<int>& queries) {\n        sort(nums.begin(), nums.end());\n        int n=nums.size();\n        int m=queries.size();\n        vector<ll> res(m);\n\n        vector<ll> pre(n, 0);    \n        // calculate prefix sum\n        pre[0] = nums[0];\n        for(int i = 1; i < n; i++) {\n            pre[i] = pre[i-1] + nums[i];\n        }\n\n        for(int i=0 ; i< m ; i++){\n            ll temp=queries[i];\n            ll ans=0;\n            ans+=findCost(nums,pre,temp);\n            res[i]=ans;\n        }\n        return res;\n    }\n};\n```\n\n
['Binary Search', 'Prefix Sum', 'C++']