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#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| 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;
}
}
|
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);
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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| 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#
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)
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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| 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
}
|
