Equal Sum Arrays With Minimum Number of Operations

Problem

You are given two arrays of integers nums1 and nums2, possibly of different lengths. The values in the arrays are between 1 and 6, inclusive.

In one operation, you can change any integer’s value in any of the arrays to any value between 1 and 6, inclusive.

Return the minimum number of operations required to make the sum of values innums1 equal to the sum of values innums2 . Return -1 if it is not possible to make the sum of the two arrays equal.

Examples

Example 1

1
2
3
4
5
6


Input: nums1 = [1,2,3,4,5,6], nums2 = [1,1,2,2,2,2]
Output: 3
Explanation: You can make the sums of nums1 and nums2 equal with 3 operations. All indices are 0-indexed.
- Change nums2[0] to 6. nums1 = [1,2,3,4,5,6], nums2 = [_**6**_ ,1,2,2,2,2].
- Change nums1[5] to 1. nums1 = [1,2,3,4,5,**_1_**], nums2 = [6,1,2,2,2,2].
- Change nums1[2] to 2. nums1 = [1,2,**_2_** ,4,5,1], nums2 = [6,1,2,2,2,2].

Example 2

1
2
3


Input: nums1 = [1,1,1,1,1,1,1], nums2 = [6]
Output: -1
Explanation: There is no way to decrease the sum of nums1 or to increase the sum of nums2 to make them equal.

Example 3

1
2
3
4
5
6


Input: nums1 = [6,6], nums2 = [1]
Output: 3
Explanation: You can make the sums of nums1 and nums2 equal with 3 operations. All indices are 0-indexed. 
- Change nums1[0] to 2. nums1 = [**_2_** ,6], nums2 = [1].
- Change nums1[1] to 2. nums1 = [2,**_2_**], nums2 = [1].
- Change nums2[0] to 4. nums1 = [2,2], nums2 = [**_4_**].

Constraints

1 <= nums1.length, nums2.length <= 10^5
1 <= nums1[i], nums2[i] <= 6

Solution

Method 1 – Greedy Counting

Intuition

To make the sums equal, we want to maximize the reduction of the difference in each operation. We can either increase the smallest values or decrease the largest values, always picking the operation that reduces the difference the most at each step.

Approach

Calculate the sums of both arrays. If already equal, return 0.
If the sum of nums1 is less than nums2, swap them so that nums1 always has the larger sum.
For each value in nums1, the maximum decrease is val - 1. For each value in nums2, the maximum increase is 6 - val.
Collect all possible changes (decreases and increases) in a list.
Sort the list in descending order.
Greedily apply the largest possible change until the difference is reduced to 0 or less, counting the number of operations.
If not possible, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution {
public:
    int minOperations(vector<int>& nums1, vector<int>& nums2) {
        int s1 = accumulate(nums1.begin(), nums1.end(), 0);
        int s2 = accumulate(nums2.begin(), nums2.end(), 0);
        if (s1 == s2) return 0;
        if (s1 < s2) return minOperations(nums2, nums1);
        vector<int> changes;
        for (int x : nums1) changes.push_back(x - 1);
        for (int x : nums2) changes.push_back(6 - x);
        sort(changes.rbegin(), changes.rend());
        int diff = s1 - s2, ops = 0;
        for (int c : changes) {
            diff -= c;
            ops++;
            if (diff <= 0) return ops;
        }
        return -1;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


func minOperations(nums1, nums2 []int) int {
    s1, s2 := 0, 0
    for _, x := range nums1 { s1 += x }
    for _, x := range nums2 { s2 += x }
    if s1 == s2 { return 0 }
    if s1 < s2 { return minOperations(nums2, nums1) }
    changes := []int{}
    for _, x := range nums1 { changes = append(changes, x-1) }
    for _, x := range nums2 { changes = append(changes, 6-x) }
    sort.Sort(sort.Reverse(sort.IntSlice(changes)))
    diff, ops := s1-s2, 0
    for _, c := range changes {
        diff -= c
        ops++
        if diff <= 0 { return ops }
    }
    return -1
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution {
    public int minOperations(int[] nums1, int[] nums2) {
        int s1 = 0, s2 = 0;
        for (int x : nums1) s1 += x;
        for (int x : nums2) s2 += x;
        if (s1 == s2) return 0;
        if (s1 < s2) return minOperations(nums2, nums1);
        List<Integer> changes = new ArrayList<>();
        for (int x : nums1) changes.add(x - 1);
        for (int x : nums2) changes.add(6 - x);
        changes.sort(Collections.reverseOrder());
        int diff = s1 - s2, ops = 0;
        for (int c : changes) {
            diff -= c;
            ops++;
            if (diff <= 0) return ops;
        }
        return -1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution {
    fun minOperations(nums1: IntArray, nums2: IntArray): Int {
        var s1 = nums1.sum()
        var s2 = nums2.sum()
        if (s1 == s2) return 0
        if (s1 < s2) return minOperations(nums2, nums1)
        val changes = mutableListOf<Int>()
        for (x in nums1) changes.add(x - 1)
        for (x in nums2) changes.add(6 - x)
        changes.sortDescending()
        var diff = s1 - s2
        var ops = 0
        for (c in changes) {
            diff -= c
            ops++
            if (diff <= 0) return ops
        }
        return -1
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution:
    def minOperations(self, nums1: list[int], nums2: list[int]) -> int:
        s1, s2 = sum(nums1), sum(nums2)
        if s1 == s2:
            return 0
        if s1 < s2:
            return self.minOperations(nums2, nums1)
        changes = [x - 1 for x in nums1] + [6 - x for x in nums2]
        changes.sort(reverse=True)
        diff, ops = s1 - s2, 0
        for c in changes:
            diff -= c
            ops += 1
            if diff <= 0:
                return ops
        return -1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


impl Solution {
    pub fn min_operations(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
        let s1: i32 = nums1.iter().sum();
        let s2: i32 = nums2.iter().sum();
        if s1 == s2 { return 0; }
        if s1 < s2 { return Solution::min_operations(nums2, nums1); }
        let mut changes: Vec<i32> = nums1.iter().map(|&x| x-1).chain(nums2.iter().map(|&x| 6-x)).collect();
        changes.sort_unstable_by(|a, b| b.cmp(a));
        let mut diff = s1 - s2;
        for (ops, c) in changes.iter().enumerate() {
            diff -= c;
            if diff <= 0 { return (ops+1) as i32; }
        }
        -1
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution {
    minOperations(nums1: number[], nums2: number[]): number {
        let s1 = nums1.reduce((a, b) => a + b, 0);
        let s2 = nums2.reduce((a, b) => a + b, 0);
        if (s1 === s2) return 0;
        if (s1 < s2) return this.minOperations(nums2, nums1);
        const changes = [...nums1.map(x => x - 1), ...nums2.map(x => 6 - x)];
        changes.sort((a, b) => b - a);
        let diff = s1 - s2, ops = 0;
        for (const c of changes) {
            diff -= c;
            ops++;
            if (diff <= 0) return ops;
        }
        return -1;
    }
}

Complexity

⏰ Time complexity: O(n log n) where n is the total number of elements in both arrays (for sorting).
🧺 Space complexity: O(n) for the changes array.

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Constraints#

Solution#

Method 1 – Greedy Counting#

Intuition#

Approach#

Code#

Complexity#