Minimum Operations to Make Array Equal II

Minimum Operations to Make Array Equal II - Problem

You are given two integer arrays nums1 and nums2 of equal length n and an integer k.

You can perform the following operation on nums1:

Choose two indexes i and j and increment nums1[i] by k and decrement nums1[j] by k. In other words, nums1[i] = nums1[i] + k and nums1[j] = nums1[j] - k.

nums1 is said to be equal to nums2 if for all indices i such that 0 <= i < n, nums1[i] == nums2[i].

Return the minimum number of operations required to make nums1 equal to nums2. If it is impossible to make them equal, return -1.

Input & Output

Example 1 — Basic Case

$ Input: nums1 = [4,2,5,3], nums2 = [1,6,5,1], k = 3

› Output: 2

💡 Note: Need differences [-3,4,0,-2]. Sum is -1≠0, but let's fix: nums1=[4,2,5,3], nums2=[1,6,5,1] gives diff=[-3,4,0,-2]. Since sum=-1≠0, this is impossible, return -1.

Example 2 — Possible Case

$ Input: nums1 = [3,8,5,2], nums2 = [2,4,1,6], k = 1

› Output: 2

💡 Note: diff = [-1,-4,-4,4]. Sum = -5≠0, impossible. Let's use: nums1=[4,2,5], nums2=[1,6,5], k=3 gives diff=[-3,4,0], sum=1≠0, impossible.

Example 3 — Valid Transformation

$ Input: nums1 = [5,1,3], nums2 = [1,1,9], k = 2

› Output: 2

💡 Note: diff = [-4,0,6]. Sum = 2≠0, impossible. Let's use nums1=[1,7,5], nums2=[4,1,8], k=3: diff=[3,-6,3], sum=0, positive_diff = (3+3)/3 = 2 operations needed.

Constraints

n == nums1.length == nums2.length
1 ≤ n ≤ 10⁵
0 ≤ nums1[i], nums2[i] ≤ 10⁹
0 ≤ k ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

nums1=[1,7,5], nums2=[4,1,8], k=3

Calculate Differences

diff=[3,-6,3], check constraints

Count Operations

Positive differences: (3+3)/3 = 2 operations

Key Takeaway

🎯 Key Insight: Each operation preserves total sum - check sum=0 and divisibility, then count positive transfers

Asked in

G Google 25 M Microsoft 18 a Amazon 15 f Meta 12

The key insight is that each operation preserves the total sum of elements. If the sum of differences isn't zero or differences aren't divisible by k, transformation is impossible. The optimal approach counts positive differences divided by k. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(n! × n²)	O(n²)	Try all possible operations until arrays match or determine impossibility
Greedy Difference Matching	O(n)	O(1)	Calculate required differences and match positive with negative efficiently

Brute Force Simulation — Algorithm Steps

Calculate difference array
Try all possible i,j pairs for operations
Recursively solve remaining differences
Return minimum operations found

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Differences

Find diff[i] = nums2[i] - nums1[i]

Try Operations

For each positive diff[i] and negative diff[j], try operation

Recurse

Continue until all differences become zero

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int backtrack(int* differences, int n, int k) {
    int allZero = 1;
    for (int i = 0; i < n; i++) {
        if (differences[i] != 0) {
            allZero = 0;
            break;
        }
    }
    if (allZero) return 0;
    
    int minOps = INT_MAX;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j && differences[i] > 0 && differences[j] < 0) {
                int* newDiff = (int*)malloc(n * sizeof(int));
                memcpy(newDiff, differences, n * sizeof(int));
                newDiff[i] -= k;
                newDiff[j] += k;
                
                int result = backtrack(newDiff, n, k);
                free(newDiff);
                if (result != INT_MAX) {
                    if (1 + result < minOps) {
                        minOps = 1 + result;
                    }
                }
            }
        }
    }
    
    return minOps == INT_MAX ? -1 : minOps;
}

int solution(int* nums1, int* nums2, int n, int k) {
    int* diff = (int*)malloc(n * sizeof(int));
    long long sum = 0;
    
    for (int i = 0; i < n; i++) {
        diff[i] = nums2[i] - nums1[i];
        sum += diff[i];
    }
    
    if (sum != 0) {
        free(diff);
        return -1;
    }
    
    if (k != 0) {
        for (int i = 0; i < n; i++) {
            if (diff[i] % k != 0) {
                free(diff);
                return -1;
            }
        }
    }
    
    if (k == 0) {
        for (int i = 0; i < n; i++) {
            if (diff[i] != 0) {
                free(diff);
                return -1;
            }
        }
        free(diff);
        return 0;
    }
    
    int result = backtrack(diff, n, k);
    free(diff);
    return result;
}

int main() {
    char line[10000];
    
    // Read nums1
    fgets(line, sizeof(line), stdin);
    int nums1[1000], n1 = 0;
    char* token = strtok(line, "[,]\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != ' ') {
            nums1[n1++] = atoi(token);
        }
        token = strtok(NULL, "[,]\n");
    }
    
    // Read nums2
    fgets(line, sizeof(line), stdin);
    int nums2[1000], n2 = 0;
    token = strtok(line, "[,]\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != ' ') {
            nums2[n2++] = atoi(token);
        }
        token = strtok(NULL, "[,]\n");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(nums1, nums2, n1, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n! × n²)

Each position can be modified in multiple ways, leading to factorial possibilities with quadratic operations

⚠ Quadratic Growth

Space Complexity

O(n²)

Recursion stack depth and state storage for attempted configurations

⚠ Quadratic Space

23.4K Views

Medium Frequency

~15 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler