Welcome to Subscribe On Youtube

2333. Minimum Sum of Squared Difference

Description

You are given two positive 0-indexed integer arrays nums1 and nums2, both of length n.

The sum of squared difference of arrays nums1 and nums2 is defined as the sum of (nums1[i] - nums2[i])2 for each 0 <= i < n.

You are also given two positive integers k1 and k2. You can modify any of the elements of nums1 by +1 or -1 at most k1 times. Similarly, you can modify any of the elements of nums2 by +1 or -1 at most k2 times.

Return the minimum sum of squared difference after modifying array nums1 at most k1 times and modifying array nums2 at most k2 times.

Note: You are allowed to modify the array elements to become negative integers.

 

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.

 

Constraints:

  • n == nums1.length == nums2.length
  • 1 <= n <= 105
  • 0 <= nums1[i], nums2[i] <= 105
  • 0 <= k1, k2 <= 109

Solutions

  • class Solution {
        public long minSumSquareDiff(int[] nums1, int[] nums2, int k1, int k2) {
            int n = nums1.length;
            int[] d = new int[n];
            long s = 0;
            int mx = 0;
            int k = k1 + k2;
            for (int i = 0; i < n; ++i) {
                d[i] = Math.abs(nums1[i] - nums2[i]);
                s += d[i];
                mx = Math.max(mx, d[i]);
            }
            if (s <= k) {
                return 0;
            }
            int left = 0, right = mx;
            while (left < right) {
                int mid = (left + right) >> 1;
                long t = 0;
                for (int v : d) {
                    t += Math.max(v - mid, 0);
                }
                if (t <= k) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            for (int i = 0; i < n; ++i) {
                k -= Math.max(0, d[i] - left);
                d[i] = Math.min(d[i], left);
            }
            for (int i = 0; i < n && k > 0; ++i) {
                if (d[i] == left) {
                    --k;
                    --d[i];
                }
            }
            long ans = 0;
            for (int v : d) {
                ans += (long) v * v;
            }
            return ans;
        }
    }
    
  • using ll = long long;
    
    class Solution {
    public:
        long long minSumSquareDiff(vector<int>& nums1, vector<int>& nums2, int k1, int k2) {
            int n = nums1.size();
            vector<int> d(n);
            ll s = 0;
            int mx = 0;
            int k = k1 + k2;
            for (int i = 0; i < n; ++i) {
                d[i] = abs(nums1[i] - nums2[i]);
                s += d[i];
                mx = max(mx, d[i]);
            }
            if (s <= k) return 0;
            int left = 0, right = mx;
            while (left < right) {
                int mid = (left + right) >> 1;
                ll t = 0;
                for (int v : d) t += max(v - mid, 0);
                if (t <= k)
                    right = mid;
                else
                    left = mid + 1;
            }
            for (int i = 0; i < n; ++i) {
                k -= max(0, d[i] - left);
                d[i] = min(d[i], left);
            }
            for (int i = 0; i < n && k; ++i) {
                if (d[i] == left) {
                    --k;
                    --d[i];
                }
            }
            ll ans = 0;
            for (int v : d) ans += 1ll * v * v;
            return ans;
        }
    };
    
  • class Solution:
        def minSumSquareDiff(
            self, nums1: List[int], nums2: List[int], k1: int, k2: int
        ) -> int:
            d = [abs(a - b) for a, b in zip(nums1, nums2)]
            k = k1 + k2
            if sum(d) <= k:
                return 0
            left, right = 0, max(d)
            while left < right:
                mid = (left + right) >> 1
                if sum(max(v - mid, 0) for v in d) <= k:
                    right = mid
                else:
                    left = mid + 1
            for i, v in enumerate(d):
                d[i] = min(left, v)
                k -= max(0, v - left)
            for i, v in enumerate(d):
                if k == 0:
                    break
                if v == left:
                    k -= 1
                    d[i] -= 1
            return sum(v * v for v in d)
    
    
  • func minSumSquareDiff(nums1 []int, nums2 []int, k1 int, k2 int) int64 {
    	k := k1 + k2
    	s, mx := 0, 0
    	n := len(nums1)
    	d := make([]int, n)
    	for i, v := range nums1 {
    		d[i] = abs(v - nums2[i])
    		s += d[i]
    		mx = max(mx, d[i])
    	}
    	if s <= k {
    		return 0
    	}
    	left, right := 0, mx
    	for left < right {
    		mid := (left + right) >> 1
    		t := 0
    		for _, v := range d {
    			t += max(v-mid, 0)
    		}
    		if t <= k {
    			right = mid
    		} else {
    			left = mid + 1
    		}
    	}
    	for i, v := range d {
    		k -= max(v-left, 0)
    		d[i] = min(v, left)
    	}
    	for i, v := range d {
    		if k <= 0 {
    			break
    		}
    		if v == left {
    			d[i]--
    			k--
    		}
    	}
    	ans := 0
    	for _, v := range d {
    		ans += v * v
    	}
    	return int64(ans)
    }
    
    func abs(x int) int {
    	if x < 0 {
    		return -x
    	}
    	return x
    }
    

All Problems

All Solutions