Count how many subsets achieve the maximum possible bitwise OR.
Problem
You are given an array of non-negative integers nums. Consider every non-empty subset of nums, and compute the bitwise OR of all elements in that subset.
Your task is to return the number of subsets whose bitwise OR is as large as possible among all subsets.
A subset is formed by choosing any collection of indices from the array, and different choices of indices count as different subsets even if they contain the same values.
Input Format
- An integer array
nums.
Output Format
- Return the number of non-empty subsets whose bitwise OR equals the maximum OR obtainable from any subset of
nums.
Constraints
1 <= nums.length <= 160 <= nums[i] <= $10^{5}$
Hints
- First determine the target OR value using all elements.
- Then count subsets that reach that exact OR value using enumeration or a subset DP style approach.
Input Format
nums: integer array of non-negative values
Output Format
- An integer representing the number of non-empty subsets whose OR equals the maximum possible OR
Constraints
1 <= nums.length <= 160 <= nums[i] <= $10^{5}$
Example 1
Input
nums = [3, 1]
Output
2
Explanation
The maximum OR is 3. The subsets [3] and [3, 1] both have OR 3, so the answer is 2.
Example 2
Input
nums = [2, 2, 2]
Output
7
Explanation
Every non-empty subset has OR 2, which is the maximum possible OR. There are $2^{3}-1$ = 7 non-empty subsets.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.