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 <= 161 <= nums[i] <= 105
Solutions
Solution 1: DFS
The maximum bitwise OR value mx in the array nums can be obtained by performing bitwise OR on all elements in the array.
Then we can use depth-first search to enumerate all subsets and count the number of subsets whose bitwise OR equals mx. We design a function dfs(i, t), which represents the number of subsets starting from index i with the current bitwise OR value being t. Initially, i = 0 and t = 0.
In the function dfs(i, t), if i equals the array length, it means we have enumerated all elements. At this point, if t equals mx, we increment the answer by one. Otherwise, we can choose to either exclude the current element nums[i] or include the current element nums[i], so we can recursively call dfs(i + 1, t) and dfs(i + 1, t | nums[i]).
Finally, we return the answer.
The time complexity is O(2n), and the space complexity is O(n), where n is the length of the array nums.
PythonJavaC++GoTypeScriptRust
class Solution:
def countMaxOrSubsets(self, nums: List[int]) -> int:
def dfs(i, t):
nonlocal ans, mx
if i == len(nums):
if t == mx:
ans += 1
return
dfs(i + 1, t)
dfs(i + 1, t | nums[i])
ans = 0
mx = reduce(lambda x, y: x | y, nums)
dfs(0, 0)
return ans(code-box)
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]);
}
}(code-box)
class Solution {
public:
int countMaxOrSubsets(vector<int>& nums) {
int ans = 0;
int mx = accumulate(nums.begin(), nums.end(), 0, bit_or<int>());
auto dfs = [&](this auto&& dfs, int i, int t) {
if (i == nums.size()) {
if (t == mx) {
ans++;
}
return;
}
dfs(i + 1, t);
dfs(i + 1, t | nums[i]);
};
dfs(0, 0);
return ans;
}
};(code-box)
func countMaxOrSubsets(nums []int) (ans int) {
mx := 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
}(code-box)
function countMaxOrSubsets(nums: number[]): number {
let ans = 0;
const mx = nums.reduce((x, y) => x | y, 0);
const dfs = (i: number, t: number) => {
if (i === nums.length) {
if (t === mx) {
ans++;
}
return;
}
dfs(i + 1, t);
dfs(i + 1, t | nums[i]);
};
dfs(0, 0);
return ans;
}(code-box)
impl Solution {
pub fn count_max_or_subsets(nums: Vec<i32>) -> i32 {
let mut ans = 0;
let mx = nums.iter().fold(0, |x, &y| x | y);
fn dfs(i: usize, t: i32, nums: &Vec<i32>, mx: i32, ans: &mut i32) {
if i == nums.len() {
if t == mx {
*ans += 1;
}
return;
}
dfs(i + 1, t, nums, mx, ans);
dfs(i + 1, t | nums[i], nums, mx, ans);
}
dfs(0, 0, &nums, mx, &mut ans);
ans
}
}(code-box)
Solution 2: Binary Enumeration
We can use binary enumeration to count the bitwise OR results of all subsets. For an array nums of length n, we can use an integer mask to represent a subset, where the i-th bit of mask being 1 means including element nums[i], and 0 means not including it.
We can iterate through all possible mask values from 0 to 2n - 1. For each mask, we can calculate the bitwise OR result of the corresponding subset and update the maximum value mx and answer ans.
The time complexity is O(2n · n), where n is the length of the array nums. The space complexity is O(1).
PythonJavaC++GoTypeScriptRust
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(code-box)
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;
}
}(code-box)
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;
}
};(code-box)
func countMaxOrSubsets(nums []int) (ans int) {
n := len(nums)
mx := 0
for mask := 0; 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
}(code-box)
function countMaxOrSubsets(nums: number[]): number {
const n = nums.length;
let ans = 0;
let mx = 0;
for (let mask = 0; mask < 1 << n; mask++) {
let t = 0;
for (let 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;
}(code-box)
impl Solution {
pub fn count_max_or_subsets(nums: Vec<i32>) -> i32 {
let n = nums.len();
let mut ans = 0;
let mut mx = 0;
for mask in 0..(1 << n) {
let mut t = 0;
for i in 0..n {
if (mask >> i) & 1 == 1 {
t |= nums[i];
}
}
if mx < t {
mx = t;
ans = 1;
} else if mx == t {
ans += 1;
}
}
ans
}
}(code-box)
