Bit Manipulation
Array
Math
Dynamic Programming
Bitmask
Description
You are given an integer array nums
.
You should move each element of nums
into one of the two arrays A
and B
such that A
and B
are non-empty, and average(A) == average(B)
.
Return true
if it is possible to achieve that and false
otherwise.
Note that for an array arr
, average(arr)
is the sum of all the elements of arr
over the length of arr
.
Example 1:
Input: nums = [1,2,3,4,5,6,7,8]
Output: true
Explanation: We can split the array into [1,4,5,8] and [2,3,6,7], and both of them have an average of 4.5.
Example 2:
Input: nums = [3,1]
Output: false
Constraints:
1 <= nums.length <= 30
0 <= nums[i] <= 104
Solutions
Solution 1
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 class Solution :
def splitArraySameAverage ( self , nums : List [ int ]) -> bool :
n = len ( nums )
if n == 1 :
return False
s = sum ( nums )
for i , v in enumerate ( nums ):
nums [ i ] = v * n - s
m = n >> 1
vis = set ()
for i in range ( 1 , 1 << m ):
t = sum ( v for j , v in enumerate ( nums [: m ]) if i >> j & 1 )
if t == 0 :
return True
vis . add ( t )
for i in range ( 1 , 1 << ( n - m )):
t = sum ( v for j , v in enumerate ( nums [ m :]) if i >> j & 1 )
if t == 0 or ( i != ( 1 << ( n - m )) - 1 and - t in vis ):
return True
return False
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
36
37
38 class Solution {
public boolean splitArraySameAverage ( int [] nums ) {
int n = nums . length ;
if ( n == 1 ) {
return false ;
}
int s = Arrays . stream ( nums ). sum ();
for ( int i = 0 ; i < n ; ++ i ) {
nums [ i ] = nums [ i ] * n - s ;
}
int m = n >> 1 ;
Set < Integer > vis = new HashSet <> ();
for ( int i = 1 ; i < 1 << m ; ++ i ) {
int t = 0 ;
for ( int j = 0 ; j < m ; ++ j ) {
if ((( i >> j ) & 1 ) == 1 ) {
t += nums [ j ] ;
}
}
if ( t == 0 ) {
return true ;
}
vis . add ( t );
}
for ( int i = 1 ; i < 1 << ( n - m ); ++ i ) {
int t = 0 ;
for ( int j = 0 ; j < ( n - m ); ++ j ) {
if ((( i >> j ) & 1 ) == 1 ) {
t += nums [ m + j ] ;
}
}
if ( t == 0 || ( i != ( 1 << ( n - m )) - 1 ) && vis . contains ( - t )) {
return true ;
}
}
return false ;
}
}
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 class Solution {
public :
bool splitArraySameAverage ( vector < int >& nums ) {
int n = nums . size ();
if ( n == 1 ) return false ;
int s = accumulate ( nums . begin (), nums . end (), 0 );
for ( int & v : nums ) v = v * n - s ;
int m = n >> 1 ;
unordered_set < int > vis ;
for ( int i = 1 ; i < 1 << m ; ++ i ) {
int t = 0 ;
for ( int j = 0 ; j < m ; ++ j )
if ( i >> j & 1 ) t += nums [ j ];
if ( t == 0 ) return true ;
vis . insert ( t );
}
for ( int i = 1 ; i < 1 << ( n - m ); ++ i ) {
int t = 0 ;
for ( int j = 0 ; j < ( n - m ); ++ j )
if ( i >> j & 1 ) t += nums [ m + j ];
if ( t == 0 || ( i != ( 1 << ( n - m )) - 1 && vis . count ( - t ))) return true ;
}
return false ;
}
};
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
36
37
38
39 func splitArraySameAverage ( nums [] int ) bool {
n := len ( nums )
if n == 1 {
return false
}
s := 0
for _ , v := range nums {
s += v
}
for i , v := range nums {
nums [ i ] = v * n - s
}
m := n >> 1
vis := map [ int ] bool {}
for i := 1 ; i < 1 << m ; i ++ {
t := 0
for j , v := range nums [: m ] {
if ( i >> j & 1 ) == 1 {
t += v
}
}
if t == 0 {
return true
}
vis [ t ] = true
}
for i := 1 ; i < 1 << ( n - m ); i ++ {
t := 0
for j , v := range nums [ m :] {
if ( i >> j & 1 ) == 1 {
t += v
}
}
if t == 0 || ( i != ( 1 << ( n - m )) - 1 && vis [ - t ]) {
return true
}
}
return false
}
GitHub