Count Number of Maximum Bitwise-OR Subsets

Medium Topics Company Tags

Consider all nonempty subsets of indices in nums. Return how many of them produce the largest possible bitwise OR of their selected values. Different choices of indices count separately, even when their values are equal.

Example 1:

Input: nums = [1,2,3]

Output: 5

Explanation: The maximum OR is 3. The five qualifying subsets are [3], [1,2], [1,3], [2,3], and [1,2,3].

Example 2:

Input: nums = [4,4]

Output: 3

Explanation: Either individual index gives OR 4, and selecting both also gives OR 4. These are three different subsets of indices.

Example 3:

Input: nums = [8]

Output: 1

Explanation: There is only one nonempty subset, containing 8, so it is the only subset with the maximum OR.

Constraints:

  • 1 <= nums.length <= 16
  • 1 <= nums[i] <= 100000


Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.