Coding Interview PatternsCount Number of Maximum Bitwise-OR Subsets
MediumSubsets
Count Number of Maximum Bitwise-OR Subsets
Explanation & Solution
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 that have this 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).
Input:nums = [3,1]
0
3
1
1
Output: 2
Explanation: The maximum possible bitwise OR of a subset is 3. The subsets with OR equal to 3 are [3] and [3,1], so the answer is 2.
Constraints
1 <= nums.length <= 161 <= nums[i] <= 10^5
Approach
Subsets pattern
1. Compute the Maximum OR
- OR all elements together:
maxOr = nums[0] | nums[1] | ... | nums[n-1] - This is the maximum possible OR since adding more elements can only set more bits
- Any subset's OR can be at most this value
2. Enumerate All Subsets
- Use backtracking to explore every possible subset
- At each index, make two choices: include the element or exclude it
- Track the running OR value through the recursion
3. Count Matching Subsets
- When the end of the array is reached, check if the current OR equals
maxOr - If it does, increment the count
- This naturally excludes the empty subset since its OR is 0 (which won't match unless maxOr is 0, but nums[i] >= 1)
4. Return the Count
- After exploring all 2^n subsets, return the total count of subsets achieving the maximum OR
Key Insight
- The maximum OR is always achieved by OR-ing all elements, since OR can only set bits, never unset them
- We enumerate all 2^n subsets, which is feasible because
n <= 16(at most 65,536 subsets)
Time
O(2^n) to enumerate all subsetsSpace
O(n) for the recursion stackVisualization
Input:
[3, 1]
—
No animation available
Left (L)Right (R)ConvergedDone
0 steps