Welcome to Subscribe On Youtube
1775. Equal Sum Arrays With Minimum Number of Operations
Description
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] <= 6
Solutions
Solution 1: Sorting
We use $s_1$ and $s_2$ to represent the sum of the arrays nums1 and nums2 respectively.
If $s_1 = s_2$, no operation is required and $0$ is returned directly. Otherwise, we might as well set $s_1 \lt s_2$, that is, the sum of the elements in $nums_1$ is less than the sum of the elements in $nums_2$, then the difference between the sum of the elements of the two arrays is $d=s_2-s_1$.
To make the sum of the two array elements equal, we need to increase the elements in nums1 and decrease the elements in nums2.
For each element $v$ in nums1, we can increase it up to $6$, so $v$ can increase by $6-v$. For each element $v$ in nums2, we can reduce it to at most $1$, then $v$ can be reduced by $v-1$.
We put the variation of each element into the array arr and then sort the array arr in descending order.
Next, we start from the first element of the array arr, greedily subtract the change of each element from $d$ until $d \leq 0$, and return the number of operations at this time.
After the traversal is completed, if $d \gt 0$, it means that the sum of the two array elements cannot be made equal, and $-1$ is returned.
The time complexity is $O((m+n) \times \log (m + n))$, and the space complexity is $O(m+n)$. Where $m$ and $n$ are the lengths of the arrays nums1 and nums2 respectively.
Solution 2
In method one, we need to create the array arr and sort it, which has high time and space complexity. Since the range of the elements in the array arr is $[0,..5]$, we create an array cnt with a length of $6$ to count the number of each element in the array arr, that is, the number of elements with the maximum variation.
Next, we start from the maximum change $i=5$, greedily subtract the maximum change from $d$ until $d \leq 0$, and return the number of operations at this time.
Time complexity $O(m+n)$, space complexity $O(C)$. Where $m$ and $n$ are the lengths of the arrays nums1 and nums2 respectively. In this question $C=6$.
-
class Solution { public int minOperations(int[] nums1, int[] nums2) { int s1 = Arrays.stream(nums1).sum(); int s2 = Arrays.stream(nums2).sum(); if (s1 == s2) { return 0; } if (s1 > s2) { return minOperations(nums2, nums1); } int d = s2 - s1; int[] arr = new int[nums1.length + nums2.length]; int k = 0; for (int v : nums1) { arr[k++] = 6 - v; } for (int v : nums2) { arr[k++] = v - 1; } Arrays.sort(arr); for (int i = 1, j = arr.length - 1; j >= 0; ++i, --j) { d -= arr[j]; if (d <= 0) { return i; } } return -1; } } // Solution 2 class Solution { public int minOperations(int[] nums1, int[] nums2) { int s1 = Arrays.stream(nums1).sum(); int s2 = Arrays.stream(nums2).sum(); if (s1 == s2) { return 0; } if (s1 > s2) { return minOperations(nums2, nums1); } int d = s2 - s1; int[] cnt = new int[6]; for (int v : nums1) { ++cnt[6 - v]; } for (int v : nums2) { ++cnt[v - 1]; } int ans = 0; for (int i = 5; i > 0; --i) { while (cnt[i] > 0 && d > 0) { d -= i; --cnt[i]; ++ans; } } return d <= 0 ? ans : -1; } } -
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); int d = s2 - s1; int arr[nums1.size() + nums2.size()]; int k = 0; for (int& v : nums1) arr[k++] = 6 - v; for (int& v : nums2) arr[k++] = v - 1; sort(arr, arr + k, greater<>()); for (int i = 0; i < k; ++i) { d -= arr[i]; if (d <= 0) return i + 1; } return -1; } }; // Solution 2 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); int d = s2 - s1; int cnt[6] = {0}; for (int& v : nums1) ++cnt[6 - v]; for (int& v : nums2) ++cnt[v - 1]; int ans = 0; for (int i = 5; i; --i) { while (cnt[i] && d > 0) { d -= i; --cnt[i]; ++ans; } } return d <= 0 ? ans : -1; } }; -
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) arr = [6 - v for v in nums1] + [v - 1 for v in nums2] d = s2 - s1 for i, v in enumerate(sorted(arr, reverse=True), 1): d -= v if d <= 0: return i return -1 # Solution 2 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) cnt = Counter([6 - v for v in nums1] + [v - 1 for v in nums2]) d = s2 - s1 ans = 0 for i in range(5, 0, -1): while cnt[i] and d > 0: d -= i cnt[i] -= 1 ans += 1 return ans if d <= 0 else -1 -
func minOperations(nums1 []int, nums2 []int) int { s1, s2 := sum(nums1), sum(nums2) if s1 == s2 { return 0 } if s1 > s2 { return minOperations(nums2, nums1) } d := s2 - s1 arr := []int{} for _, v := range nums1 { arr = append(arr, 6-v) } for _, v := range nums2 { arr = append(arr, v-1) } sort.Sort(sort.Reverse(sort.IntSlice(arr))) for i, v := range arr { d -= v if d <= 0 { return i + 1 } } return -1 } func sum(nums []int) (s int) { for _, v := range nums { s += v } return } // Solution 2 func minOperations(nums1 []int, nums2 []int) (ans int) { s1, s2 := sum(nums1), sum(nums2) if s1 == s2 { return 0 } if s1 > s2 { return minOperations(nums2, nums1) } d := s2 - s1 cnt := [6]int{} for _, v := range nums1 { cnt[6-v]++ } for _, v := range nums2 { cnt[v-1]++ } for i := 5; i > 0; i-- { for cnt[i] > 0 && d > 0 { d -= i cnt[i]-- ans++ } } if d <= 0 { return } return -1 } func sum(nums []int) (s int) { for _, v := range nums { s += v } return }