Solution

Method 1 – Prefix Sum & Binary Search

Intuition

To make all elements equal to a target value, the minimum number of operations is the sum of absolute differences between each element and the target. By sorting the array and using prefix sums, we can efficiently answer each query.

Approach

Sort nums and compute prefix sums.
For each query, use binary search to find the position where query would be inserted.
For elements less than query, total operations = query * count - sum of those elements.
For elements greater than or equal to query, total operations = sum of those elements - query * count.
Add both to get the answer for each query.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    vector<long long> minOperations(vector<int>& nums, vector<int>& queries) {\n        sort(nums.begin(), nums.end());\n        int n = nums.size();\n        vector<long long> pre(n + 1, 0), ans;\n        for (int i = 0; i < n; ++i) pre[i + 1] = pre[i] + nums[i];\n        for (int q : queries) {\n            int idx = lower_bound(nums.begin(), nums.end(), q) - nums.begin();\n            long long left = (long long)q * idx - pre[idx];\n            long long right = pre[n] - pre[idx] - (long long)q * (n - idx);\n            ans.push_back(left + right);\n        }\n        return ans;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">    vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">long</span><span style=\"color:#D73A49;--shiki-dark:#F97583\"> long</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">> </span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">minOperations</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">></span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x26;</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> nums</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">, </span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">></span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x26;</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> queries</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">) {</span></span>\n<span class=\"line\"><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">        sort</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(nums.</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">begin</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(), nums.</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">e

Related Tags