Spend Unit Changes to Minimize Squared Pair Differences
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Given equal-length arrays `nums1` and `nums2`, minimize `sum((nums1[i] - nums2[i])^2)`. One operation changes one entry by `+1` or `-1`. You may use at most `k1` operations on `nums1` and at most `k2` on `nums2`. Modified entries may become negative. Return the minimum sum as a `long long`.
```cpp
class Solution {
public:
long long minSumSquareDiff(vector<int>& nums1, vector<int>& nums2, int k1, int k2);
};
```
### Examples
**Example 1:**
```text
Input: nums1 = [1,5], nums2 = [4,5], k1 = 1, k2 = 1
Output: 1
Explanation: The only nonzero difference is 3. Two unit changes reduce it to 1, whose square is 1.
```
**Example 2:**
```text
Input: nums1 = [0,2], nums2 = [0,2], k1 = 3, k2 = 0
Output: 0
Explanation: The arrays already agree. Since operations are optional, use none and retain total zero.
```
### Constraints
- `1 <= n == nums1.length == nums2.length <= 100000`.
- `0 <= nums1[i], nums2[i] <= 100000`.
- `0 <= k1, k2 <= 10^9`.
### Clarifying Questions
- Must every allowed operation be used? No; both budgets are upper limits.
- Can entries become negative? Yes. Initial entries and budgets may also be zero.
- Is an operation a change to one entry or the whole array? It changes one entry by one.
- Must modified arrays be returned? No; return only the minimum sum.
```hint Check the boundary
Check arrays that already agree when an operation budget remains unused.
```
Overview: Minimize the sum of squared corresponding differences between two arrays using bounded unit changes on either array.