Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Every subarray ending at the current element is either that element alone or a previous ending subarray extended by it. Only the OR values matter, so equal results can be merged. Extending a subarray can turn bits on but never off, limiting the distinct ending values to roughly the bit width rather than the number of starting positions.

Approach

Maintain a set of OR values for subarrays ending at the previous position and a global result set.
For each value x, create a new set containing x and x | previousOr for every previous ending value.
Replace the ending set and merge it into the global set. A fresh set prevents mixing states from different endpoints.
Return the global set's size, which counts distinct OR results rather than subarrays.

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

        for x in arr:
            temp = set()
            for y in curr:
                temp.add(x | y)
            temp.add(x)
            curr = temp
            # curr = {x | y for y in curr} | {x}
            res |= curr

        return len(res)

Complexity analysis

Let n = arr.length and B be the integer bit width. At most B + 1 distinct OR values can end at one position, so time is O(nB). The global result set can contain O(nB) values, giving O(nB) auxiliary space (O(n) for fixed-width integers).