Problem
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).
Examples
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]
Solution
Video explanation
Here is the video explaining below methods in detail. Please check it out:
Method 1 - Backtracking
When we have to compute the maximum bitwise OR of subsets, since OR operations are cumulative (meaning that once a bit is set, it remains set), including more elements in a subset typically brings the result closer to the maximum possible OR value. Therefore, after computing the maximum OR, we can count how many subsets achieve this maximum. So, the problem boils down to:
- Compute the Maximum OR by combining all the elements in the array.
- Explore Every Subset of the array and count how many subsets yield this maximum OR value.
The key insight here is that the more elements we OR together, the higher the resultant OR value tends to be. This makes backtracking a suitable method to systematically explore each subset, ensuring we account for all possible combinations.
So, here is the approach:
- Compute Maximum OR: First, determine the maximum possible OR value by applying the | (bitwise OR) operation to all elements in the array. This value represents the highest OR any subset can achieve.
- Backtracking: Then, use backtracking to explore all potential subsets. Calculate the OR value for each subset. If it equals the maximum OR, increment the counter. This is similar to Subsets Problem.
- Base Case: When the OR of a subset matches the maximum, count it. Continue recursively exploring all subsets until all options have been examined.
Code
Java
class Solution {
private int[] nums; // Array to store input numbers
private int maxOr; // Variable to store the maximum OR value
public int countMaxOrSubsets(int[] nums) {
this.nums = nums;
int maxOr = 0;
// Step 1: Compute the maximum OR by combining all elements
for (int num : nums) {
maxOr |= num; // Bitwise OR operation with the current number
}
this.maxOr = maxOr; // Store the maximum OR value
// Step 2: Use DFS to count the subsets that achieve the maximum OR
return dfs(0, 0); // Start DFS with index 0 and current OR value 0
}
// DFS function to explore all subsets
private int dfs(int idx, int currOr) {
// Base case: If we've considered all elements
if (idx == nums.length) {
return currOr == maxOr ? 1 : 0; // Return 1 if current OR equals max OR, otherwise return 0
}
// Consider two cases:
// 1. Including nums[idx] in the current subset
int include = dfs(idx + 1, currOr | nums[idx]);
// 2. Excluding nums[idx] from the current subset
int exclude = dfs(idx + 1, currOr);
// Return the sum of both cases
return include + exclude;
}
}
Python
class Solution:
def __init__(self):
self.nums = []
self.max_or = 0
def countMaxOrSubsets(self, nums):
self.nums = nums
self.max_or = 0
# Step 1: Compute the maximum OR
for num in nums:
self.max_or |= num
# Step 2: Backtrack to count the subsets
return self.dfs(0, 0)
def dfs(self, idx, current_or):
if idx == len(self.nums):
return 1 if current_or == self.max_or else 0
# Consider two cases: including nums[idx] or excluding nums[idx]
include = self.dfs(idx + 1, current_or | self.nums[idx])
exclude = self.dfs(idx + 1, current_or)
return include + exclude
Complexity
- ⏰ Time complexity:
O(n.2^n), since the total number of subsets is2^n, wherenis the length of the array. For each subset, we compute theOR, which takesO(n). - 🧺 Space complexity:
O(n), for using recursion stack.
Method 2 - Using Caching
Code
Java
class Solution {
private int[] nums;
private int maxOr;
private Map<String, Integer> memo;
public int countMaxOrSubsets(int[] nums) {
this.nums = nums;
this.maxOr = 0;
this.memo = new HashMap<>();
// Step 1: Compute the maximum OR
for (int num : nums) {
maxOr |= num;
}
// Step 2: Use a recursive function with caching to count the subsets
return dfs(0, 0);
}
private int dfs(int idx, int currentOr) {
if (idx == nums.length) {
return currentOr == maxOr ? 1 : 0;
}
String key = idx + "," + currentOr;
if (memo.containsKey(key)) {
return memo.get(key);
}
// Consider two cases: including nums[idx] or excluding nums[idx]
int include = dfs(idx + 1, currentOr | nums[idx]);
int exclude = dfs(idx + 1, currentOr);
int result = include + exclude;
memo.put(key, result);
return result;
}
}
Python
class Solution:
def countMaxOrSubsets(self, nums: List[int]) -> int:
self.nums = nums
self.max_or = 0
# Step 1: Compute the maximum OR
for num in nums:
self.max_or |= num
# Step 2: Use a recursive function with caching to count the subsets
@lru_cache(None)
def dfs(idx, current_or):
if idx == len(nums):
return 1 if current_or == self.max_or else 0
# Consider two cases: including nums[idx] or excluding nums[idx]
include = dfs(idx + 1, current_or | nums[idx])
exclude = dfs(idx + 1, current_or)
return include + exclude
# Initialize the count with the first index and OR value 0
return dfs(0, 0)
Complexity
- ⏰ Time complexity:
O(n.2^n) - 🧺 Space complexity:
O(n * maxOr)as idx goes from0 to n-1andcurrOrgoes from0tomaxOr