Problem of The Day: Bitwise ORs of Subarrays

Problem Statement

leetcode problem link

Brute Force [TLE]

class Solution:
    def subarrayBitwiseORs(self, arr: List[int]) -> int:
        N = len(arr)
        res = set()
        for i in range(N):
            curr = arr[i]
            res.add(curr)
            for j in range(i + 1, N):
                curr |= arr[j]
                res.add(curr)

        return len(res)

Approach 1: Frontier Set

class Solution(object):
    def subarrayBitwiseORs(self, A):
        ans = set()
        cur = {0}
        for x in A:
            cur = {x | y for y in cur} | {x}
            ans |= cur
        return len(ans)