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 <= 16
1 <= nums[i] <= 105
Solutions
Solution 1: DFS
The maximum bitwise OR value \(\textit{mx}\) in the array \(\textit{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 \(\textit{mx}\). We design a function \(\text{dfs(i, t)}\), which represents the number of subsets starting from index \(\textit{i}\) with the current bitwise OR value being \(\textit{t}\). Initially, \(\textit{i} = 0\) and \(\textit{t} = 0\).
In the function \(\text{dfs(i, t)}\), if \(\textit{i}\) equals the array length, it means we have enumerated all elements. At this point, if \(\textit{t}\) equals \(\textit{mx}\), we increment the answer by one. Otherwise, we can choose to either exclude the current element \(\textit{nums[i]}\) or include the current element \(\textit{nums[i]}\), so we can recursively call \(\text{dfs(i + 1, t)}\) and \(\text{dfs(i + 1, t | nums[i])}\).
Finally, we return the answer.
The time complexity is \(O(2^n)\), and the space complexity is \(O(n)\), where \(n\) is the length of the array \(\textit{nums}\).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
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 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
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)\).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
|