Welcome to Subscribe On Youtube
2044. Count Number of Maximum Bitwise-OR Subsets
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.
Solution 2: Binary Enumeration
We can use binary enumeration to count the bitwise OR results of all subsets. For an array $\textit{nums}$ of length $n$, we can use an integer $\textit{mask}$ to represent a subset, where the $i$-th bit of $\textit{mask}$ being 1 means including element $\textit{nums[i]}$, and 0 means not including it.
We can iterate through all possible $\textit{mask}$ values from $0$ to $2^n - 1$. For each $\textit{mask}$, we can calculate the bitwise OR result of the corresponding subset and update the maximum value $\textit{mx}$ and answer $\textit{ans}$.
The time complexity is $O(2^n \cdot n)$, where $n$ is the length of the array $\textit{nums}$. The space complexity is $O(1)$.
-
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]); } } // Solution 2 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; } } -
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]); } }; // Solution 2 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; } }; -
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 # Solution 2 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 -
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 } // Solution 2 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 } -
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; } // Solution 2 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; } -
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 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 } } -
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; } } -
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; } }; -
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 -
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 } -
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; } -
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 } }