#2333
Minimum Sum of Squared Difference
expert · 1145 · lc medium +32 · verified · 26.8% accepted · 669 likes · top 5%
Description
You are given two 0-indexed positive integer arrays nums1 and nums2 of equal length n.
The sum of squared differences is defined as the sum of (nums1[i] - nums2[i])2 for all 0 <= i < n.
You may change elements of nums1 by +1 or -1 at most k1 times total, and elements of nums2 by +1 or -1 at most k2 times total.
Return the minimum achievable sum of squared differences. Elements may become negative.
Example 1:
Input: nums1 = [1,2,3,4], nums2 = [2,10,20,19], k1 = 0, k2 = 0
Output: 579
Explanation: The elements in nums1 and nums2 cannot be modified because k1 = 0 and k2 = 0.
The sum of square difference will be: (1 - 2)2 + (2 - 10)2 + (3 - 20)2 + (4 - 19)2 = 579.
Example 2:
Input: nums1 = [1,4,10,12], nums2 = [5,8,6,9], k1 = 1, k2 = 1
Output: 43
Explanation: One way to obtain the minimum sum of square difference is:
- Increase nums1[0] once.
- Increase nums2[2] once.
The minimum of the sum of square difference will be:
(2 - 5)2 + (4 - 8)2 + (10 - 7)2 + (12 - 9)2 = 43.
Note that, there are other ways to obtain the minimum of the sum of square difference, but there is no way to obtain a sum smaller than 43.
Code
1
2
3