Leetcode Daily Question 18/10/2024 - 2044. Count Number of Maximum Bitwise-OR Subsets

Problem Description:

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).

from typing import List
class Solution:
  def countMaxOrSubsets(self, nums: List[int]) -> int:
    maximum_OR = 0
    for num in nums:
      maximum_OR |= num
    
    count = 0
    def dfs(index, curr_OR):
      nonlocal count
      
      if index == len(nums):
        if curr_OR == maximum_OR:
          count += 1
        return
      
      dfs(index + 1, curr_OR | nums[index])
      dfs(index + 1, curr_OR)
      
    dfs(0,0)
    return count

Explanation:

To solve this, we first note the behaviour of the bitwise OR operator. The OR operator will set the bit as long as at least one of the two bits being compared is set.

0 OR 0 = 0
1 OR 0 = 1
1 OR 1 = 1

So, by continuously performing OR operations on more and more integers, the number of bits set will never decrease.

This means that the maximum bitwise OR of an array is the bitwise OR of all the elements in that array.

maximum_OR = 0
for num in nums:
  maximum_OR |= num

Using this, we can traverse all possible subsets to count the number of subsets with maximum bitwise OR.

We can do this by dfs. We can look for elements or combinations that must be part of subsets to reach the maximum OR, and count how many such combinations there are.

count = 0
def dfs(index, curr_OR):
  nonlocal count
  
  if index == len(nums): # Reached the end of the array
    if curr_OR == maximum_OR:
      count += 1
    return
  
  dfs(index + 1, curr_OR | nums[index]) # Include the current number
  dfs(index + 1, curr_OR) # Exclude the current number

dfs(0, 0)
return count

The time complexity is O(2^n) as there are 2^n possible subsets given an integer array of size n.

The space complexity is O(1) as we only store constant variables

The full solution can be found near the top of the page.