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] <= 105This approach involves generating all subsets using a bitmask. For each possible subset generated by the bitmask, compute the bitwise OR, and keep track of the maximum bitwise OR found. After calculating the OR for all subsets, we count how many subsets achieved the maximum OR value.
This solution uses a recursive helper function countMaxOrSubsets which explores all possible subsets of the input array by deciding whether to include each element in the current subset. The function keeps track of the current subset’s bitwise OR and updates the global maximum OR and corresponding count of subsets achieving this OR as necessary.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * 2^n), where n is the length of the array. There are 2^n possible subsets and computing the OR for each subset can take O(n) in the worst case.
Space Complexity: O(n) due to recursive call stack depth.
This approach employs an iterative method utilizing bitmasks to evaluate all potential subsets. For each possible subset marked by a bitmask, the bitwise OR is computed and retained if it represents a new maximum. The process counts how many subsets reach this maximal OR value, iterating over binary number representations to dynamically include or exclude each number in the subset.
The C solution iteratively calculates OR values for subsets encoded through bitmasks, iterating through possible subset representations and dynamically including elements based on bit positions, updating the maximum OR and associated subset count as it runs.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * 2^n) - By iterating through all 2^n subsets and calculating ORs, computation scales linearly with each set size.
Space Complexity: O(1), since only fixed local variables manage computations.
| Approach | Complexity |
|---|---|
| Recursive Enumeration with Bitmasking | Time Complexity: O(n * 2^n), where n is the length of the array. There are 2^n possible subsets and computing the OR for each subset can take O(n) in the worst case. |
| Iterative Bitmasking | Time Complexity: O(n * 2^n) - By iterating through all 2^n subsets and calculating ORs, computation scales linearly with each set size. |
Count Number of Maximum Bitwise-OR Subsets - Leetcode 2044 - Python • NeetCodeIO • 9,197 views views
Watch 9 more video solutions →Practice Count Number of Maximum Bitwise-OR Subsets with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor