898.md

898 Bitwise ORs of Subarrays

Description

link

---

Solution

Assume B[i][j] = A[i] | A[i+1] | ... | A[j] Hash set cur stores all wise B[0][i], B[1][i], B[2][i], B[i][i].

When we handle the A[i+1], we want to update cur So we need operate bitwise OR on all elements in cur. Also we need to add A[i+1] to cur.

In each turn, we add all elements in cur to res.

Code

Complexity T : O(30N) M : O(N)

class Solution:
    def subarrayBitwiseORs(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        res, cur = set(), set()
        for i in A:
            cur = {i | j for j in cur} | {i}
            res |= cur
        return len(res)