• Posts

Problem 2044 Count Number of Maximum Bitwise-OR Subsets

Problem Statement

Link - Problem 2044

Question

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 <= 16
• 1 <= nums[i] <= 105

Solution

class Solution {
public:
    int countMaxOrSubsets(vector<int>& nums) {
        int n = nums.size();
        int maxOrValue = 0;
        for (int num : nums) {
            maxOrValue |= num;
        }

        vector<vector<int>> memo(n, vector<int>(maxOrValue + 1, -1));

        return countSubsetsRecursive(nums, 0, 0, maxOrValue, memo);
    }

private:
    int countSubsetsRecursive(vector<int>& nums, int index, int currentOr, int targetOr, vector<vector<int>>& memo) {

        if (index == nums.size()) {
            return (currentOr == targetOr) ? 1 : 0;
        }

        if (memo[index][currentOr] != -1) {
            return memo[index][currentOr];
        }

        int countWithout = countSubsetsRecursive(nums, index + 1, currentOr, targetOr, memo);

        int countWith = countSubsetsRecursive(nums, index + 1, currentOr | nums[index], targetOr, memo);

        return memo[index][currentOr] = countWithout + countWith;
    }
};

Complexity Analysis

| Algorithm                   | Time Complexity | Space Complexity |
| --------------------------- | --------------- | ---------------- |
| Memoized Depth-First Search | O(n 2^n)        | O(n 2^n )        |

Explanation

Intial Thoughts

To approach this problem, we should first consider the properties of bitwise OR operations. The maximum possible bitwise OR of a subset can be obtained by including all elements in the subset. Then, we need to find the number of subsets that have this maximum bitwise OR. We should also consider the concept of subsets and how to generate them. Additionally, we should think about how to optimize the solution to avoid unnecessary computations. The problem can be broken down into smaller sub-problems, such as finding the maximum bitwise OR and counting the number of subsets with this maximum value. We can use a recursive approach or dynamic programming to solve this problem. The time complexity and space complexity of the solution should also be considered.

Intuitive Analysis

Intuitively, we can think of the problem as finding the number of ways to combine the elements in the array to get the maximum possible bitwise OR. This can be achieved by considering each element in the array and deciding whether to include it in the subset or not. We can use a tree-like structure to represent the possible subsets, where each node represents a decision to include or exclude an element. The maximum bitwise OR can be obtained by considering the elements with the most significant bits set. We can also use the concept of memoization to store the results of sub-problems and avoid redundant computations. By analyzing the problem intuitively, we can develop a solution that is both efficient and effective. The key is to find a balance between exploring all possible subsets and avoiding unnecessary computations. We should also consider the constraints of the problem, such as the size of the input array, to optimize the solution.

1. Intuition

• The problem requires finding the maximum possible bitwise OR of a subset of the given array and then counting the number of different non-empty subsets with this maximum bitwise OR.
• To solve this, we need to consider all possible subsets of the given array and calculate their bitwise OR.
• The maximum possible bitwise OR of a subset can be obtained by performing a bitwise OR operation on all elements of the array.
• We can use recursion to generate all possible subsets and calculate their bitwise OR.
• To optimize the solution, we can use memoization to store the results of subproblems and avoid redundant calculations.
• The base case for the recursion is when the index reaches the end of the array, in which case we check if the current bitwise OR is equal to the target bitwise OR.
• The recursive case involves two possibilities: including the current element in the subset or excluding it.
• By considering both possibilities, we can count the number of subsets with the maximum bitwise OR.

2. Implementation

• We start by initializing the maxOrValue variable to 0 and then perform a bitwise OR operation on all elements of the array using maxOrValue |= num.
• We create a 2D vector memo to store the results of subproblems, where memo[index][currentOr] represents the count of subsets with the current bitwise OR at the given index.
• The countSubsetsRecursive function takes four parameters: nums, index, currentOr, and targetOr, and returns the count of subsets with the maximum bitwise OR.
• Inside the countSubsetsRecursive function, we check if the index has reached the end of the array, in which case we return 1 if the current bitwise OR is equal to the target bitwise OR, and 0 otherwise.
• We also check if the result of the subproblem is already stored in the memo vector, in which case we return the stored value.
• If not, we recursively call the countSubsetsRecursive function twice: once including the current element in the subset and once excluding it, and store the result in the memo vector.
• Finally, we return the count of subsets with the maximum bitwise OR by calling the countSubsetsRecursive function with the initial index and current bitwise OR.

Complexity Analysis

Time Complexity:

• The algorithm uses countSubsetsRecursive function, which has a time complexity of O(2^n * n) because in the worst-case scenario, it needs to explore all possible subsets of the input array nums. The for loop at the beginning of countMaxOrSubsets function takes O(n) time to calculate maxOrValue, but it’s dominated by the recursive calls.
• The recursive function makes two calls: countSubsetsRecursive with index + 1 and currentOr, and another with index + 1 and currentOr | nums[index]. These calls result in a binary tree with height n, leading to 2^n possible paths. Each path takes O(n) time to calculate the currentOr value using the | operator.
• Therefore, the overall time complexity is O(2^n _ n) because the algorithm needs to explore all possible subsets and perform a constant amount of work for each subset. This can be represented mathematically as T(n) = 2^n _ n, where T(n) is the time complexity and n is the size of the input array.

Space Complexity:

• The algorithm uses a memo table to store the results of subproblems, which has a space complexity of O(2^n * n) because it needs to store the results for all possible subsets of the input array nums. The memo table has n rows and maxOrValue + 1 columns.
• The recursive function call stack can go up to a depth of n, resulting in a space complexity of O(n) due to the recursive call stack. However, this is dominated by the space complexity of the memo table.
• Therefore, the overall space complexity is O(2^n _ n) because the algorithm needs to store the results of all possible subsets in the memo table. This can be represented mathematically as S(n) = 2^n _ n, where S(n) is the space complexity and n is the size of the input array.

Footnote

This question is rated as Medium difficulty.

Hints

Can we enumerate all possible subsets?

The maximum bitwise-OR is the bitwise-OR of the whole array.

Similar Questions: