Count Number of Maximum Bitwise-OR Subsets

Problem Description

Given an integer array nums, you need to determine the maximum possible bitwise OR that any non-empty subset of nums can achieve, and then count how many different non-empty subsets yield this maximum bitwise OR. A subset is defined by selecting some (or all) numbers based on their indices, and two subsets are different if they choose different indices.

Key Insights

• The maximum bitwise OR is achieved by OR-ing all elements in the array.
• Since the array length is at most 16, it is feasible to iterate over all 2^n possible subsets (excluding the empty subset) using bitmask enumeration.
• For each subset, compute the bitwise OR of its elements and compare it with the maximum OR.
• Count only those subsets whose OR equals the maximum OR.

Space and Time Complexity

Time Complexity: O(2^n * n), where n is the number of elements in the array.
Space Complexity: O(1) extra space (not counting the space for input).

Solution

The solution uses a brute force bitmask enumeration approach:

1. First, compute the maximum OR by iterating through the array and OR-ing all its elements.
2. Then, iterate through all possible non-empty subsets by treating each subset as a bitmask from 1 to 2^n - 1.
3. For each subset, compute its bitwise OR by checking every bit in the mask; if the bit is set, OR the corresponding element to an accumulator.
4. If the computed OR equals the maximum OR, increment the subset count.
5. Finally, return the count.

This algorithm leverages bit manipulation and enumeration techniques to efficiently test every subset given the small constraint (n ≤ 16).

Code Solutions