Count Number of Maximum Bitwise-OR Subsets
MedPrompt
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] <= 105
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves generating every possible non-empty subset of the input array nums. For each subset, we calculate the bitwise OR of its elements. We can determine the maximum OR value and count the subsets that achieve it in a single pass. A common and straightforward way to represent and iterate through all subsets for a small number of elements is by using a bitmask.
Algorithm
- This approach can be implemented with a single pass.
- Initialize
maxOr = 0andcount = 0. - Iterate through all possible non-empty subsets using a bitmask
ifrom1to(1 << n) - 1, wherenis the length ofnums. - For each mask
i, calculate thecurrentOrof the corresponding subset. A numbernums[j]is in the subset if thej-th bit ofiis set. - Compare
currentOrwithmaxOr:- If
currentOr > maxOr, a new maximum OR value is found. UpdatemaxOr = currentOrand resetcountto1. - If
currentOr == maxOr, another subset with the maximum OR value is found. Incrementcount.
- If
- After iterating through all masks,
countwill hold the number of subsets with the maximum bitwise OR.
Walkthrough
A bitmask is an integer used to represent a set. For an array of size n, we can use an n-bit integer where the j-th bit corresponds to the j-th element of the array. If the bit is 1, the element is in the subset; if it's 0, it's not. We can loop from 1 to 2^n - 1 to generate all non-empty subsets.
class Solution { public int countMaxOrSubsets(int[] nums) { int n = nums.length; int maxOr = 0; int count = 0; // Iterate through all 2^n - 1 non-empty subsets using a bitmask. // Each 'i' represents a subset. for (int i = 1; i < (1 << n); i++) { int currentOr = 0; // For each subset, calculate its bitwise OR. for (int j = 0; j < n; j++) { // Check if the j-th element is in the current subset. if (((i >> j) & 1) == 1) { currentOr |= nums[j]; } } // Compare the current subset's OR with the max OR found so far. if (currentOr > maxOr) { maxOr = currentOr; count = 1; } else if (currentOr == maxOr) { count++; } } return count; }}Complexity
Time
O(n * 2^n). We iterate through `2^n - 1` subsets. For each subset, we iterate through up to `n` elements to check for inclusion and calculate the bitwise OR.
Space
O(1). We only use a few variables to store the maximum OR value and the count, regardless of the input size.
Trade-offs
Pros
Simple to understand and implement.
Uses constant extra space.
Cons
This is the least efficient approach due to its time complexity. For each of the
2^nsubsets, it iterates up tontimes to calculate the OR value.
This approach uses recursion to explore all possible subsets. A recursive function is defined to build subsets by making a decision at each step: either include the current element in the subset or not. This avoids the nested loop structure of the bitmasking approach, leading to a better time complexity by removing the multiplicative factor of n.
Algorithm
- Initialize global variables
maxOr = 0andcount = 0. - Define a recursive function
backtrack(index, currentOr)which explores subsets. - Base Case: When
indexreaches the end of the array (nums.length), a full subset has been considered.- If its
currentOris greater thanmaxOr, we've found a new maximum. UpdatemaxOrand resetcountto 1. - If its
currentOrequalsmaxOr, we've found another subset with the same maximum. Incrementcount.
- If its
- Recursive Step: For the element at
nums[index], make two recursive calls:- To exclude the current element:
backtrack(index + 1, currentOr). - To include the current element:
backtrack(index + 1, currentOr | nums[index]).
- To exclude the current element:
- Start the process by calling
backtrack(0, 0). The initial call withcurrentOr = 0represents the empty subset. Sincenums[i] >= 1, the finalmaxOrwill be greater than 0, so the empty subset will not be part of the final count.
Walkthrough
The backtracking function explores the decision tree of subsets. Each node in the tree represents a decision to include or exclude an element. The leaves of the tree correspond to the 2^n possible subsets. By passing the currentOr value down the recursion, we build the OR value incrementally, which is more efficient than re-calculating it from scratch for every subset.
class Solution { private int maxOr = 0; private int count = 0; public int countMaxOrSubsets(int[] nums) { backtrack(nums, 0, 0); return count; } private void backtrack(int[] nums, int index, int currentOr) { // Base case: we've processed all elements. if (index == nums.length) { if (currentOr > maxOr) { maxOr = currentOr; count = 1; } else if (currentOr == maxOr) { // This check handles the case where maxOr could be 0, but // problem constraints (nums[i] >= 1) ensure maxOr > 0. count++; } return; } // Recursive step: two choices for nums[index] // Choice 1: Exclude nums[index] backtrack(nums, index + 1, currentOr); // Choice 2: Include nums[index] backtrack(nums, index + 1, currentOr | nums[index]); }}Complexity
Time
O(2^n). The recursion tree has `2^n` leaves (subsets), and we do constant work at each node in the tree.
Space
O(n). The maximum depth of the recursion stack is `n`, corresponding to the length of the input array.
Trade-offs
Pros
More efficient than the brute-force bitmasking approach with a time complexity of O(2^n) instead of O(n * 2^n).
The logic is a classic application of backtracking for subset problems.
Cons
While more efficient than the bitmasking approach, its time complexity is still exponential.
It uses O(n) space for the recursion stack, unlike the O(1) space of the iterative bitmasking approach.
This is the most efficient approach. It improves upon standard backtracking by first determining the target maximum bitwise OR value. Then, a second recursive pass counts the subsets that achieve this target OR. This separation allows for a powerful pruning optimization: once a subset's OR reaches the maximum possible value, we can immediately calculate how many supersets can be formed from it without exploring them one by one.
Algorithm
- Step 1: Find the Maximum OR Value. The maximum possible bitwise OR of any subset is simply the bitwise OR of all elements in
nums. This is because the OR operation is monotonic (a | b >= a). Calculate thistargetOr. - Step 2: Count Subsets with Backtracking.
- Define a recursive function
backtrack(index, currentOr). - Pruning: If at any point
currentOr == targetOr, we have found a subset that achieves the maximum OR. Any subset of the remainingnums.length - indexelements can be added to this current subset, and the OR will remaintargetOr. The number of such subsets is2^(nums.length - index). Add this to a globalcountand return, pruning this entire branch of the search. - Base Case: If
index == nums.length, return. This is only reached if thetargetOrwas not achieved on this path. - Recursive Step: Make two calls: one excluding
nums[index]and one including it.
- Define a recursive function
- Start by calling
backtrack(0, 0)and return the finalcount.
Walkthrough
The key insight is that OR(subset) <= OR(all elements). The maximum OR is therefore the OR of all elements. We can pre-calculate this value. Then, during our backtracking search, if a partial subset S formed from the first i elements has an OR equal to the maximum, any subset S' formed by adding elements from the remaining n-i elements will also have the same OR. There are 2^(n-i) such subsets S', so we can add this number to our count and stop exploring that path.
class Solution { private int count = 0; private int targetOr = 0; public int countMaxOrSubsets(int[] nums) { // Step 1: Find the maximum possible OR value. for (int num : nums) { targetOr |= num; } // Step 2: Use backtracking with pruning to count subsets. backtrack(nums, 0, 0); return count; } private void backtrack(int[] nums, int index, int currentOr) { // Pruning condition: if current OR is already the max, all subsequent // subsets formed from this path will also have the max OR. if (currentOr == targetOr) { int remainingElements = nums.length - index; count += 1 << remainingElements; // Add 2^remainingElements to the count return; } // Base case: reached the end of the array. if (index == nums.length) { return; } // Recursive step // Choice 1: Exclude nums[index] backtrack(nums, index + 1, currentOr); // Choice 2: Include nums[index] backtrack(nums, index + 1, currentOr | nums[index]); }}Complexity
Time
O(2^n). While the worst-case complexity is the same as standard backtracking, the average-case performance is much better due to pruning.
Space
O(n). The space is dominated by the depth of the recursion stack.
Trade-offs
Pros
The most efficient approach due to the pruning strategy.
Significantly faster than other approaches on average, as many recursive branches can be skipped.
The logic is clean and separates the problem into two distinct steps.
Cons
The worst-case time complexity remains exponential, as pruning may not be effective on all inputs.
Solutions
Solution
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]); }}class Solution {public: int mx; int ans; vector<int> nums; int countMaxOrSubsets(vector<int> &nums) { this->nums = nums; mx = 0; ans = 0; for (int x : nums) mx |= x; dfs(0, 0); return ans; } void dfs(int i, int t) { if (i == nums.size()) { if (t == mx) ++ans; return; } dfs(i + 1, t); dfs(i + 1, t | nums[i]); }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.