[Leetcode] 898. Bitwise ORs of Subarrays

https://leetcode.com/problems/bitwise-ors-of-subarrays/?envType=daily-question&envId=2025-07-31

initial

generating all possible or values for every subarray (contiguous, cannot delete elements in between) is the question.

im thinking of creating 2 lists of odd and even checks and iterating through each number that is converted to binary and if that bit index is 1 we mark the odd list index as true and like that and after processing all if both checks are true i multiply 2 to answer and continue and else i just multiply 1. But if its like 1,2,4, its 001,010,100, so technically this will be doing 222=8 which is def wrong

Key logic

(a | b) | c = a | (b | c)
so taking all ORs from previous subarray and ORing with current number gives new subarrays ending at that current number.

sol

then i thought of using prefix sum like [1,3,7] but still that didnt catch the pattern.

the key realisation is that for OR, OR can only flip 0->1, but NOT 1->0. If we have a million numbers and we OR those million numbers with a single number, the number of possible unique values is bound by the number of bit positions (32). Thats cuz most of them will collapse to the same value that we saw before

10 in binary: 1010

When we OR any number with 1010:
- Position 3: MUST be 1 (forced by the 1 in 1010)
- Position 2: can be 0 or 1 (depends on the other number)  
- Position 1: MUST be 1 (forced by the 1 in 1010)
- Position 0: can be 0 or 1 (depends on the other number)

So the result pattern is: 1_1_
Where _ can be either 0 or 1
so either 0 or 1 can fill those blanks so it is 2*2

Previous OR values: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, ...} (100+ numbers)
New number: 8 (binary: 1000)

Let's see what happens:
1 | 8 = 0001 | 1000 = 1001 = 9
2 | 8 = 0010 | 1000 = 1010 = 10  
3 | 8 = 0011 | 1000 = 1011 = 11
4 | 8 = 0100 | 1000 = 1100 = 12
5 | 8 = 0101 | 1000 = 1101 = 13
6 | 8 = 0110 | 1000 = 1110 = 14
7 | 8 = 0111 | 1000 = 1111 = 15
8 | 8 = 1000 | 1000 = 1000 = 8
9 | 8 = 1001 | 1000 = 1001 = 9  ← Same as 1|8!
10| 8 = 1010 | 1000 = 1010 = 10 ← Same as 2|8!
11| 8 = 1011 | 1000 = 1011 = 11 ← Same as 3|8!

This distinct OR value fact tells us that we dont need to track all poss OR values but just the distinct ones

class Solution:
    def subarrayBitwiseORs(self, nums: List[int]) -> int:
        global_set=set()
        local_set=set()
        for num in nums:
            tmp=set()
            for prev_num in local_set:
                tmp.add(num|prev_num)
            tmp.add(num)
            local_set=tmp
            global_set.update(tmp)
        return len(global_set)

more optimised with set comprehension and union
much better

class Solution:
    def subarrayBitwiseORs(self, nums: List[int]) -> int:
        global_set = set()
        local_set = set()
        
        for num in nums:
            local_set = {num | prev_num for prev_num in local_set} | {num}
            global_set |= local_set
        
        return len(global_set)

the first | is the OR operation and the second | is the union like set1 | set2 = set1+set2

num = 4
local_set = {1, 2}

# Step 1: Set comprehension
{num | prev_num for prev_num in local_set}  # {4|1, 4|2} = {5, 6}

# Step 2: Union with {num}
{5, 6} | {4}  # = {4, 5, 6}

complexity

n32 distinct OR values from previous step time
global set can store up to n32 space in worst case