SORTING + UPPERBOUND + PREFIX SUM
Intuition\n Describe your first thoughts on how to solve this problem. \nSuppose we have a query \'a\' then we have to know the number of elements which is grea
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSuppose we have a query \'a\' then we have to know the number of elements which is greater than \'a\' and less than or equal to \'a\' in nums array and their sum Let\'s if \'b\' number is greater and \'c\' number is less than or equal to in nums array. And their sum is sa and sb. Then, if we change the all elements to \'a\' then their sum would be \'a\' * \'b\' and \'a\' * \'c\'. Then, simply add their difference value and store them.\n\nHow to find how many numbers are greater than particular query \'q\' in nums array ? \n-> Here, Comes sorting. Sort the array and use binary search or STL upperbound and find their index.\n\nHow to find the sum of numbers are greater than particular query \'q\' in nums array ?\n-> Use the concept of prefix sum\n\n# Complexity\n- Time complexity: $$O(m * log(n))$$\n- m = length of queries array\n- n = length of nums array\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n- n = length of nums array\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    vector<long long> minOperations(vector<int>& nums, vector<int>& Q) {\n        int m = size(Q), n = size(nums);\n        sort(begin(nums),end(nums));\n        vector<long long> ans, pf(n+1);\n        \n        for(int i=1; i<=n; ++i)\n            pf[i] = pf[i-1] + 0ll + nums[i-1];\n\n        for(int&q: Q){\n            int idx = upper_bound(begin(nums),end(nums),q) - begin(nums);\n            long long bigger = pf[n] - pf[idx], smaller = pf[idx];\n            long long bgreq = (n-idx)*1ll*q, smreq = idx*1ll*q;\n            long long e = bigger-bgreq + smreq-smaller;\n            ans.push_back(e);\n        }\n        return ans;\n    }\n};\n```
['Array', 'Binary Search', 'Sorting', 'Prefix Sum', 'C++']