Prefix Sum | Easy to Understand | Explained using Example
Intuition\nThe brute force approach would be to iterate through the queries array and for each query, iterate through the nums array to calculate the number of 
# Intuition\nThe brute force approach would be to iterate through the queries array and for each query, iterate through the nums array to calculate the number of operations for each element. However, this solution\'s time complexity is O(n*m), which doesn\'t satisfy the given constraint.\n\nAnother way is to calculate the prefix sum array, and then for each query, calculate the number of operations using the prefix sum. See the example below to understand better.\n\n### Example\nFor nums=[3,1,6,4,8] and queries=[4,2]\n\nWe will first sort the nums array and then find the index where the element becomes greater than current element.\n<!-- Describe your approach to solving the problem. -->\n![image.png](https://assets.leetcode.com/users/images/382d446e-e781-4364-8040-e589da875f9f_1679814220.262036.png)\n\n\n\n- prefix_sum= [0, 1, 4, 8, 14, 22]\n\n- left operations = (no. of elements smaller or equal to q) * q - sum of smaller or equal elements to q\n\n        = idx*q - prefix_sum[idx]\n        = 3 * 4 - 8 = 4\n- right operations = sum of elements greater than q - (no. of elements greater than q) * q \n\n         = (prefix_sum[n] - prefix_sum[idx]) - (n-idx) * q\n         = 14 - 2 * 4 = 6\n\n- total operations = left+right\n    \n         = 4+6 = 10\n\nNow, it\'s your turn to dry run the above approach for q=2. \n\n# Complexity\n- Time complexity: O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n\n- Space complexity: O(n)\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>& queries) {\n        vector<long long> ans;\n        int n=nums.size();\n        sort(nums.begin(), nums.end());\n        vector<long long> prefixSum(n+1);\n\n        prefixSum[0] = 0;\n        for (int i=1;i<=n;++i) {\n            prefixSum[i] = prefixSum[i-1] + (nums[i-1]) ; // calculating the prefix sum\n        }\n        for (long long q:queries) {\n            auto itr = upper_bound(nums.begin(), nums.end(),q); // find the iterator where nums[idx]>q\n            int idx = itr-nums.begin(); \n            long long left= idx*q-prefixSum[idx]; // number of operations for smaller elements\n            long long right= (prefixSum[n]-prefixSum[idx])-(n-idx)*q; // number of operations for larger elements\n            // cout<<left<<" "<<right<<endl;\n            ans.push_back(left + right);\n        }\n        return ans;\n    }\n};\n\n```
['Prefix Sum', 'C++']