Problem Statement in English

Given an array of integers, return the number of unique bitwise OR results of all possible subarrays.

Approach

We can use a set to keep track of all unique bitwise OR results of subarrays. The idea is to iterate through the array and for each element, calculate the bitwise OR with all previously seen elements.

This way we can reuse the results of previous calculations and avoid recalculating the OR for the same subarray multiple times.

Also, since the integer will fit into a 32-bit signed integer, we can use a set to store the results without worrying about it growing too much.

Solution in Python


class Solution:
    def subarrayBitwiseORs(self, arr: List[int]) -> int:
        res = set()
        cur = set()

        for num in arr:
            cur = {num | x for x in cur} | {num}
            res.update(cur)
        
        return len(res)

Complexity

  • Time: $O(nlogw)$
    Where $n$ is the length of the array and $w$ is the size of the integer.

  • Space: $O(1)$
    There can only be 32 unique bitwise OR results for each subarray, so the space complexity is constant.

Mistakes I Made

I needed a hint to figure out how to reuse the results of previous calculations.

And we are done.