[Leetcode] 2044. Count Number of Maximum Bitwise-OR Subsets

https://leetcode.com/problems/count-number-of-maximum-bitwise-or-subsets/description/?envType=daily-question&envId=2025-07-28

initial

im thinking combination all and adding freq of every combination to map and getting the maximum key and its corresponding freq but its very time inefficient right hint dont code but is that right approach. So i couldnt think of an eff sol

sol

use dp where we have 2 options - to include the current number into subset or not. Theres a way to calculate all possible number of subsets with that method (via a dict) and storing the OR value as the key and how many subsets have that OR value as the value (freq).

one thing to note is that curernt dictionary changes in size or we need to creat a new dicitonary for each loop and update that to the old dictionary

very impt to realise pattern if [3,2,1,5]

the base case is 0:1 cuz to make 0 we just have 1 way.

Then for 3, we can include or not so 0:1,3:1
For 2, for previosu subsets of (0:1,3:1), we can include 2 or not so for 0, we can have just 0 or 0,2 -> 0:1, 2:1 and for 3, we can have 3 or 3,2 -> 3:1, and 3|2 is 3 so 3:1 so 3:2 in total. And so on

from collections import defaultdict
class Solution:
   def countMaxOrSubsets(self, nums: List[int]) -> int:
       dic=defaultdict(int)
       dic[0]=1
       max_val=0
       for num in nums:
           max_val |=num
       for num in nums:
           new_dic=defaultdict(int)
           for key,val in dic.items():
               ## option 1 - dont take this num into subset
               new_dic[key]+=val

               ## option 2 - take this num into subset
               new_dic[key|num]= new_dic[key|num]+val
           dic=new_dic
       return dic[max_val]
           

complexity

n*k time where k is number of distinct or elements stored in dic

k space