Count Number of Maximum Bitwise-OR Subsets Problem

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:

1
2
3
4
5


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:

1
2
3


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:

1
2
3
4
5
6
7
8
9


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.
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


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 is 2^n, where n is the length of the array. For each subset, we compute the OR, which takes O(n).
🧺 Space complexity: O(n), for using recursion stack.

Method 2 - Using Caching

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


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 from 0 to n-1 and currOr goes from 0 to maxOr

Problem#

Examples#

Solution#

Video explanation#

Method 1 - Backtracking#

Code#

Complexity#

Method 2 - Using Caching#

Code#

Complexity#

Problem

Examples

Solution

Video explanation

Method 1 - Backtracking

Code

Complexity

Method 2 - Using Caching

Code

Complexity