Minimum Sum of Squared Difference solution and explanation

import heapq

def min_sum_of_squares(nums1, nums2, k1, k2):
    n = len(nums1)
    # Calculate differences
    differences = [abs(a - b) for a, b in zip(nums1, nums2)]
    
    # Create a max heap
    max_heap = [-diff for diff in differences]
    heapq.heapify(max_heap)
    
    total_k = k1 + k2
    
    while total_k > 0:
        max_diff = -heapq.heappop(max_heap)
        if max_diff == 0:
            break
        
        max_diff -= 1
        total_k -= 1
        heapq.heappush(max_heap, -max_diff)
    
    # Calculate the resulting sum of squares
    result = sum(diff**2 for diff in max_heap)
    return result

# Example usage:
print(min_sum_of_squares([1, 4, 10, 12], [5, 8, 6, 9], 1, 1))  # Output: 43

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>

using namespace std;

int minSumOfSquares(vector<int>& nums1, vector<int>& nums2, int k1, int k2) {
    priority_queue<int> maxHeap;
    int n = nums1.size();
    for (int i = 0; i < n; i++) {
        maxHeap.push(abs(nums1[i] - nums2[i]));
    }

    int totalK = k1 + k2;
    while (totalK > 0 && !maxHeap.empty()) {
        int maxDiff = maxHeap.top();
        maxHeap.pop();
        if (maxDiff == 0) break;
        maxHeap.push(maxDiff - 1);
        totalK--;
    }

    int result = 0;
    while (!maxHeap.empty()) {
        int diff = maxHeap.top();
        maxHeap.pop();
        result += diff * diff;
    }
    return result;
}

int main() {
    vector<int> nums1 = {1, 4, 10, 12};
    vector<int> nums2 = {5, 8, 6, 9};
    int k1 = 1, k2 = 1;
    cout << minSumOfSquares(nums1, nums2, k1, k2) << endl; // Output: 43
    return 0;
}

import java.util.*;

public class MinSumOfSquares {
    public static int minSumOfSquares(int[] nums1, int[] nums2, int k1, int k2) {
        int n = nums1.length;
        int[] differences = new int[n];

        for (int i = 0; i < n; i++) {
            differences[i] = Math.abs(nums1[i] - nums2[i]);
        }

        Arrays.sort(differences);

        int totalK = k1 + k2;
        for (int i = n - 1; i >= 0 && totalK > 0; i--) {
            if (differences[i] > 0) {
                int decrease = Math.min(differences[i], totalK);
                differences[i] -= decrease;
                totalK -= decrease;
            }
        }

        int result = 0;
        for (int diff : differences) {
            result += diff * diff;
        }

        return result;
    }

    public static void main(String[] args) {
        int[] nums1 = {1, 4, 10, 12};
        int[] nums2 = {5, 8, 6, 9};
        int k1 = 1, k2 = 1;
        System.out.println(minSumOfSquares(nums1, nums2, k1, k2)); // Output: 43
    }
}

function minSumOfSquares(nums1, nums2, k1, k2) {
    let differences = nums1.map((v, i) => Math.abs(v - nums2[i]));
    differences.sort((a, b) => b - a);
    let totalK = k1 + k2;

    for (let i = 0; i < differences.length && totalK > 0; i++) {
        if (differences[i] > 0) {
            let decrease = Math.min(differences[i], totalK);
            differences[i] -= decrease;
            totalK -= decrease;
        }
    }

    return differences.reduce((sum, diff) => sum + diff * diff, 0);
}

// Example usage:
console.log(minSumOfSquares([1, 4, 10, 12], [5, 8, 6, 9], 1, 1)); // Output: 43

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
}