Count Number of Maximum Bitwise-OR Subsets

Medium

Asked by:

38 views

Topics:

Bit ManipulationDynamic ProgrammingRecursion

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 2³ - 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] <= 10⁵

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the input array `nums` and the range of values within `nums`?
Can the input array `nums` contain duplicate numbers, and if so, how should that affect the counting of subsets?
If multiple subsets achieve the maximum bitwise OR, should I return the *total* count of such subsets, or is there a specific requirement for how to handle that scenario?
Is an empty subset a valid subset? If so, what should be the behavior of bitwise OR on an empty set?
Can the input array `nums` be empty or null? If so, what should the return value be?

Brute Force Solution

Approach

We need to find how many groups of numbers give the highest possible combined value when combined using a special bitwise operation (OR). The brute force method simply tries every single possible group of numbers to find the maximum value.

Here's how the algorithm would work step-by-step:

First, figure out the largest possible value we could get by combining *all* the numbers together using the special bitwise operation.
Then, consider every possible group of numbers. This means trying every combination, from just one number in the group, to two numbers, to three, and so on, all the way up to using all the numbers.
For each group, calculate its combined value using the special bitwise operation.
If a group's combined value is equal to the largest possible value we found earlier, count that group.
After checking every possible group, the total count of groups that resulted in the largest possible value is the answer.

Code Implementation

def count_max_or_subsets_brute_force(numbers):
    maximum_bitwise_or = 0
    for number in numbers:
        maximum_bitwise_or |= number

    count_of_maximum_ors = 0
    number_of_elements = len(numbers)

    # Iterate through all possible subsets
    for i in range(1 << number_of_elements):
        current_bitwise_or = 0
        for j in range(number_of_elements):
            # Check if the j-th element is included in the current subset
            if (i >> j) & 1:

                current_bitwise_or |= numbers[j]

        # Count the subset if its bitwise OR equals the maximum bitwise OR
        if current_bitwise_or == maximum_bitwise_or:

            count_of_maximum_ors += 1

    return count_of_maximum_ors

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach iterates through all possible subsets of the input array. An array of size n has 2^n possible subsets. For each subset, the bitwise OR operation is performed which takes O(n) in the worst case. However, the dominant factor is generating and iterating through all subsets. Therefore, the overall time complexity is O(2^n).

Space Complexity

O(1) – The provided solution iterates through all possible subsets of the input array. The only extra space required is for storing the maximum bitwise OR value and the count of subsets that achieve this maximum. These variables use a constant amount of space regardless of the input array's size N. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The problem asks us to find how many subsets of a set of numbers have the maximum possible bitwise OR value. Instead of checking every subset, we use a technique that builds the OR value incrementally, only exploring paths that can potentially lead to the maximum OR.

Here's how the algorithm would work step-by-step:

First, calculate the maximum possible bitwise OR value achievable by taking the OR of all the numbers in the set.
Then, think of it like exploring a tree. Each level of the tree represents choosing whether or not to include a number in a subset.
At each number, we have two choices: either include it in the current subset, or don't.
If including the number increases the current subset's OR value towards the maximum, we continue down that branch of the tree.
If including the number doesn't change the subset's OR value (meaning the number's bits are already covered in the existing OR), it's still worth considering because it's another valid subset that achieves the maximum OR.
If the current subset's OR value is already equal to the maximum possible OR value, then any further numbers can be included or excluded, so we've found another subset.
Keep track of how many subsets lead to the maximum possible OR value. This count is our answer.
By only exploring paths that have the potential to lead to the maximum OR, we avoid checking unnecessary subsets, making the process efficient.

Code Implementation

def count_max_or_subsets(numbers):
    maximum_bitwise_or = 0
    for number in numbers:
        maximum_bitwise_or |= number

    count = 0

    def backtrack(index, current_or):
        nonlocal count

        if index == len(numbers):
            if current_or == maximum_bitwise_or:
                count += 1
            return

        # Explore including the current number
        backtrack(index + 1, current_or)

        # Only consider including if it contributes to max_or or is already max_or.
        if (current_or | numbers[index]) > current_or or current_or == maximum_bitwise_or:

            backtrack(index + 1, current_or | numbers[index])

    # Initiate the backtracking process.
    backtrack(0, 0)
    return count

Big(O) Analysis

Time Complexity

O(2^n) – The algorithm explores all possible subsets of the input array of size n. For each element, we have two choices: either include it in the current subset or exclude it. This leads to a binary decision tree with a depth of n. Therefore, the total number of subsets considered is 2^n, resulting in a time complexity of O(2^n). The calculation of the maximum OR value initially takes O(n) time, but this is dominated by the subset enumeration.

Space Complexity

O(N) – The algorithm employs a recursive approach that explores a decision tree of depth N, where N is the number of elements in the input set. Each level of recursion corresponds to a number in the set, and at each level, a new stack frame is created to store the current subset's OR value and the index of the current number. Therefore, the maximum depth of the recursion stack is N, resulting in O(N) auxiliary space for the call stack.

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 as there are no subsets.
Array with one element	If the element is the maximum OR, return 1; otherwise return 0.
Array with all elements equal to 0	If 0 is the maximum OR, the number of subsets is 2^n; otherwise it's 0.
Array with all elements having the same maximum OR value	The number of subsets is 2^n, where n is the array length.
Array with large numbers that might cause integer overflow during OR operation	Ensure the data type used for the OR operation can accommodate the maximum possible OR value.
Large input array that might cause recursion depth issues if using recursion	Prefer dynamic programming or iterative approach to avoid stack overflow.
Array with very few elements contributing to the maximum OR	The solution should correctly count all subsets that achieve the maximum OR, even if they are few.
All elements are powers of 2	The maximum OR is the sum of all the powers of 2, and count the subsets that result in this max OR.

Null or empty input array

How to Handle:

Return 0 as there are no subsets.

Array with one element

How to Handle:

If the element is the maximum OR, return 1; otherwise return 0.

Array with all elements equal to 0

How to Handle:

If 0 is the maximum OR, the number of subsets is 2^n; otherwise it's 0.

Array with all elements having the same maximum OR value

How to Handle:

The number of subsets is 2^n, where n is the array length.

Array with large numbers that might cause integer overflow during OR operation

How to Handle:

Ensure the data type used for the OR operation can accommodate the maximum possible OR value.

Large input array that might cause recursion depth issues if using recursion

How to Handle:

Prefer dynamic programming or iterative approach to avoid stack overflow.

Array with very few elements contributing to the maximum OR

How to Handle:

The solution should correctly count all subsets that achieve the maximum OR, even if they are few.

All elements are powers of 2

How to Handle:

The maximum OR is the sum of all the powers of 2, and count the subsets that result in this max OR.