Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2044.html
2044. Count Number of Maximum Bitwise-OR Subsets (Medium)
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
Similar Questions:
Solution 1. Bitmask
- Compute
goal
which is the maximum possible bitwise OR of a subset ofnums
, i.e. the bitwise OR of all the numbers innums
. - Enumerate all non-empty subsets of
nums
using bitmask and compute the bitwise OR of each of them. Increment answer if the subset’s bitwise OR is the same asgoal
.
-
// OJ: https://leetcode.com/problems/count-number-of-maximum-bitwise-or-subsets/ // Time: O(2^N * N) // Space: O(1) class Solution { public: int countMaxOrSubsets(vector<int>& A) { int goal = 0, N = A.size(), ans = 0; for (int n : A) goal |= n; for (int m = 1; m < 1 << N; ++m) { int x = 0; for (int i = 0; i < N; ++i) { if (m >> i & 1) x |= A[i]; } if (x == goal) ++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 ############ # 2044. Count Number of Maximum Bitwise-OR Subsets # https://leetcode.com/problems/count-number-of-maximum-bitwise-or-subsets/ class Solution: def countMaxOrSubsets(self, nums: List[int]) -> int: n = len(nums) mp = collections.defaultdict(int) mmax = float('-inf') for mask in range(1, 1 << n): s = 0 for j in range(n): if (mask >> j) & 1: s |= nums[j] mp[s] += 1 mmax = max(mmax, s) return mp[mmax]
-
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]); } }
-
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 }
-
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; }
-
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 } }
We can use DP to reduce the time complexity at the cost of space complexity
-
// OJ: https://leetcode.com/problems/count-number-of-maximum-bitwise-or-subsets/ // Time: O(2^N) // Space: O(2^N) class Solution { public: int countMaxOrSubsets(vector<int>& A) { int goal = 0, N = A.size(), ans = 0; vector<int> dp(1 << N); for (int n : A) goal |= n; for (int m = 1; m < 1 << N; ++m) { int lowbit = m & -m; dp[m] = dp[m - lowbit] | A[__builtin_ctz(lowbit)]; if (dp[m] == goal) ++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 ############ # 2044. Count Number of Maximum Bitwise-OR Subsets # https://leetcode.com/problems/count-number-of-maximum-bitwise-or-subsets/ class Solution: def countMaxOrSubsets(self, nums: List[int]) -> int: n = len(nums) mp = collections.defaultdict(int) mmax = float('-inf') for mask in range(1, 1 << n): s = 0 for j in range(n): if (mask >> j) & 1: s |= nums[j] mp[s] += 1 mmax = max(mmax, s) return mp[mmax]
-
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]); } }
-
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 }
-
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; }
-
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 } }
Discuss
https://leetcode.com/problems/count-number-of-maximum-bitwise-or-subsets/discuss/1525216/C%2B%2B-Bitmask-%2B-DP