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 in nums1 equal to the sum of values in nums2. Return -1 if it is not possible to make the sum of the two arrays equal.
Example 1:
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:
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:
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 <= 1051 <= nums1[i], nums2[i] <= 6In #1775 Equal Sum Arrays With Minimum Number of Operations, the goal is to make the sums of two arrays equal using the minimum number of operations, where each operation can change an element to any value between 1 and 6. The key observation is that each modification can either increase or decrease the total sum by a limited amount.
A common strategy is a greedy approach combined with counting. First compute the sums of both arrays. If the sums are already equal, no operations are needed. Otherwise, determine the maximum possible contribution each element can make toward reducing the difference. For the array with the smaller sum, increasing elements toward 6 helps, while for the larger sum array, decreasing elements toward 1 helps.
By counting how much each element can change the difference and always applying the largest possible improvement first, we minimize the number of operations. This method runs in O(n + m) time with small constant overhead and uses O(1) extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy with counting of possible changes | O(n + m) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Let's note that we want to either decrease the sum of the array with a larger sum or increase the array's sum with the smaller sum.
You can maintain the largest increase or decrease you can make in a binary search tree and each time get the maximum one.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this type of greedy array problem is common in technical interviews. It tests understanding of greedy decision-making, sum manipulation, and efficient counting techniques, which are frequently assessed in mid-level coding interviews.
A counting array or frequency tracking structure works well. It helps store how much each element can contribute to reducing the difference, allowing the algorithm to greedily apply the largest adjustments first.
The optimal approach uses a greedy strategy. Compute the sum difference between the arrays and track how much each element can reduce that difference by moving toward 1 or 6. Always apply the largest possible improvement first to minimize the number of operations.
Each operation has a bounded impact on the sum difference. By always choosing the change that reduces the difference the most, the algorithm ensures that the number of operations stays minimal while moving steadily toward equal sums.