Bit Manipulation
Array
Backtracking
Enumeration
Description
Given an integer array nums
, find the maximum possible bitwise OR of a subset of nums
and return the number of different non-empty subsets with the maximum bitwise OR .
An array a
is a subset of an array b
if a
can be obtained from b
by deleting some (possibly zero) elements of b
. Two subsets are considered different if the indices of the elements chosen are different.
The bitwise OR of an array a
is equal to a[0] OR a[1] OR ... OR a[a.length - 1]
(0-indexed ).
Example 1:
Input: nums = [3,1]
Output: 2
Explanation: The maximum possible bitwise OR of a subset is 3. There are 2 subsets with a bitwise OR of 3:
- [3]
- [3,1]
Example 2:
Input: nums = [2,2,2]
Output: 7
Explanation: All non-empty subsets of [2,2,2] have a bitwise OR of 2. There are 23 - 1 = 7 total subsets.
Example 3:
Input: nums = [3,2,1,5]
Output: 6
Explanation: The maximum possible bitwise OR of a subset is 7. There are 6 subsets with a bitwise OR of 7:
- [3,5]
- [3,1,5]
- [3,2,5]
- [3,2,1,5]
- [2,5]
- [2,1,5]
Constraints:
1 <= nums.length <= 16
1 <= nums[i] <= 105
Solutions
Solution 1
Python3 Java C++ Go TypeScript Rust
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 class Solution :
def countMaxOrSubsets ( self , nums : List [ int ]) -> int :
mx = ans = 0
for x in nums :
mx |= x
def dfs ( i , t ):
nonlocal mx , ans
if i == len ( nums ):
if t == mx :
ans += 1
return
dfs ( i + 1 , t )
dfs ( i + 1 , t | nums [ i ])
dfs ( 0 , 0 )
return ans
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 class Solution {
private int mx ;
private int ans ;
private int [] nums ;
public int countMaxOrSubsets ( int [] nums ) {
mx = 0 ;
for ( int x : nums ) {
mx |= x ;
}
this . nums = nums ;
dfs ( 0 , 0 );
return ans ;
}
private void dfs ( int i , int t ) {
if ( i == nums . length ) {
if ( t == mx ) {
++ ans ;
}
return ;
}
dfs ( i + 1 , t );
dfs ( i + 1 , t | nums [ i ] );
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 class Solution {
public :
int mx ;
int ans ;
vector < int > nums ;
int countMaxOrSubsets ( vector < int >& nums ) {
this -> nums = nums ;
mx = 0 ;
ans = 0 ;
for ( int x : nums ) mx |= x ;
dfs ( 0 , 0 );
return ans ;
}
void dfs ( int i , int t ) {
if ( i == nums . size ()) {
if ( t == mx ) ++ ans ;
return ;
}
dfs ( i + 1 , t );
dfs ( i + 1 , t | nums [ i ]);
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 func countMaxOrSubsets ( nums [] int ) int {
mx , ans := 0 , 0
for _ , x := range nums {
mx |= x
}
var dfs func ( i , t int )
dfs = func ( i , t int ) {
if i == len ( nums ) {
if t == mx {
ans ++
}
return
}
dfs ( i + 1 , t )
dfs ( i + 1 , t | nums [ i ])
}
dfs ( 0 , 0 )
return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 function countMaxOrSubsets ( nums : number []) : number {
let n = nums . length ;
let max = 0 ;
for ( let i = 0 ; i < n ; i ++ ) {
max |= nums [ i ];
}
let ans = 0 ;
function dfs ( pre : number , depth : number ) : void {
if ( depth == n ) {
if ( pre == max ) ++ ans ;
return ;
}
dfs ( pre , depth + 1 );
dfs ( pre | nums [ depth ], depth + 1 );
}
dfs ( 0 , 0 );
return ans ;
}
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 impl Solution {
fn dfs ( nums : & Vec < i32 > , i : usize , sum : i32 ) -> ( i32 , i32 ) {
let n = nums . len ();
let mut max = i32 :: MIN ;
let mut res = 0 ;
for j in i .. n {
let num = sum | nums [ j ];
if num >= max {
if num > max {
max = num ;
res = 0 ;
}
res += 1 ;
}
let ( r_max , r_res ) = Self :: dfs ( nums , j + 1 , num );
if r_max >= max {
if r_max > max {
max = r_max ;
res = 0 ;
}
res += r_res ;
}
}
( max , res )
}
pub fn count_max_or_subsets ( nums : Vec < i32 > ) -> i32 {
Self :: dfs ( & nums , 0 , 0 ). 1
}
}
Solution 2
Python3 Java C++ Go TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 class Solution :
def countMaxOrSubsets ( self , nums : List [ int ]) -> int :
def dfs ( u , t ):
nonlocal ans , mx
if u == len ( nums ):
if t > mx :
mx , ans = t , 1
elif t == mx :
ans += 1
return
dfs ( u + 1 , t | nums [ u ])
dfs ( u + 1 , t )
ans = mx = 0
dfs ( 0 , 0 )
return ans
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 {
private int mx ;
private int ans ;
private int [] nums ;
public int countMaxOrSubsets ( int [] nums ) {
this . nums = nums ;
dfs ( 0 , 0 );
return ans ;
}
private void dfs ( int u , int t ) {
if ( u == nums . length ) {
if ( t > mx ) {
mx = t ;
ans = 1 ;
} else if ( t == mx ) {
++ ans ;
}
return ;
}
dfs ( u + 1 , t );
dfs ( u + 1 , t | nums [ u ] );
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 class Solution {
public :
int mx ;
int ans ;
int countMaxOrSubsets ( vector < int >& nums ) {
dfs ( 0 , 0 , nums );
return ans ;
}
void dfs ( int u , int t , vector < int >& nums ) {
if ( u == nums . size ()) {
if ( t > mx ) {
mx = t ;
ans = 1 ;
} else if ( t == mx )
++ ans ;
return ;
}
dfs ( u + 1 , t , nums );
dfs ( u + 1 , t | nums [ u ], nums );
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 func countMaxOrSubsets ( nums [] int ) int {
n := len ( nums )
ans := 0
mx := 0
for mask := 1 ; mask < 1 << n ; mask ++ {
t := 0
for i , v := range nums {
if (( mask >> i ) & 1 ) == 1 {
t |= v
}
}
if mx < t {
mx = t
ans = 1
} else if mx == t {
ans ++
}
}
return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 function countMaxOrSubsets ( nums : number []) : number {
const n = nums . length ;
let res = 0 ;
let max = - Infinity ;
const dfs = ( i : number , sum : number ) => {
for ( let j = i ; j < n ; j ++ ) {
const num = sum | nums [ j ];
if ( num >= max ) {
if ( num > max ) {
max = num ;
res = 0 ;
}
res ++ ;
}
dfs ( j + 1 , num );
}
};
dfs ( 0 , 0 );
return res ;
}
Solution 3
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 class Solution :
def countMaxOrSubsets ( self , nums : List [ int ]) -> int :
n = len ( nums )
ans = 0
mx = 0
for mask in range ( 1 << n ):
t = 0
for i , v in enumerate ( nums ):
if ( mask >> i ) & 1 :
t |= v
if mx < t :
mx = t
ans = 1
elif mx == t :
ans += 1
return ans
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 countMaxOrSubsets ( int [] nums ) {
int n = nums . length ;
int ans = 0 ;
int mx = 0 ;
for ( int mask = 1 ; mask < 1 << n ; ++ mask ) {
int t = 0 ;
for ( int i = 0 ; i < n ; ++ i ) {
if ((( mask >> i ) & 1 ) == 1 ) {
t |= nums [ i ] ;
}
}
if ( mx < t ) {
mx = t ;
ans = 1 ;
} else if ( mx == t ) {
++ ans ;
}
}
return ans ;
}
}
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 countMaxOrSubsets ( vector < int >& nums ) {
int n = nums . size ();
int ans = 0 ;
int mx = 0 ;
for ( int mask = 1 ; mask < 1 << n ; ++ mask ) {
int t = 0 ;
for ( int i = 0 ; i < n ; ++ i ) {
if (( mask >> i ) & 1 ) {
t |= nums [ i ];
}
}
if ( mx < t ) {
mx = t ;
ans = 1 ;
} else if ( mx == t )
++ ans ;
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 func countMaxOrSubsets ( nums [] int ) int {
mx , ans := 0 , 0
var dfs func ( u , t int )
dfs = func ( u , t int ) {
if u == len ( nums ) {
if t > mx {
mx , ans = t , 1
} else if t == mx {
ans ++
}
return
}
dfs ( u + 1 , t )
dfs ( u + 1 , t | nums [ u ])
}
dfs ( 0 , 0 )
return ans
}