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
Approach 01:
-
C++
-
Python
class Solution { public: int countMaxOrSubsets(vector<int>& nums) { const int maxOrValue = accumulate(nums.begin(), nums.end(), 0, bit_or<>()); int subsetCount = 0; dfs(nums, 0, 0, maxOrValue, subsetCount); return subsetCount; } private: void dfs(const vector<int>& nums, int index, int currentOrValue, const int& maxOrValue, int& subsetCount) { if (index == nums.size()) { if (currentOrValue == maxOrValue) ++subsetCount; return; } dfs(nums, index + 1, currentOrValue, maxOrValue, subsetCount); dfs(nums, index + 1, currentOrValue | nums[index], maxOrValue, subsetCount); } };
class Solution: def countMaxOrSubsets(self, nums: list[int]) -> int: maxOrValue = 0 for num in nums: maxOrValue |= num # Calculate the maximum OR value subsetCount = [0] # Use a list to allow modification within dfs self.dfs(nums, 0, 0, maxOrValue, subsetCount) return subsetCount[0] # Return the count stored in the list def dfs(self, nums: list[int], index: int, currentOrValue: int, maxOrValue: int, subsetCount: list[int]) -> None: if index == len(nums): if currentOrValue == maxOrValue: subsetCount[0] += 1 # Increment the count return # Exclude the current number self.dfs(nums, index + 1, currentOrValue, maxOrValue, subsetCount) # Include the current number self.dfs(nums, index + 1, currentOrValue | nums[index], maxOrValue, subsetCount)
Time Complexity
- Subset Generation:
The function uses a depth-first search (DFS) to explore all subsets of the input vector
nums
. For a list of sizen
, there are a total of2^n
possible subsets. Hence, the DFS traversal results in a time complexity of \(O(2^n)\). - Overall Time Complexity:
As a result, the overall time complexity is \(O(2^n)\).
Space Complexity
- Call Stack:
The maximum depth of the recursion stack is
n
, wheren
is the size of the input vector. Therefore, the space complexity due to the recursion call stack is \(O(n)\). - Overall Space Complexity:
The overall space complexity is \(O(n)\).