Greedy
Array
Hash Table
Counting
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 <= 105
1 <= nums1[i], nums2[i] <= 6
Solutions
Solution 1
Python3 Java C++ Go
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
Python3 Java C++ Go
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
}
GitHub