Complexity matters

Bitwise ORs of Subarrays - LeetCode

Complexity is O(30N). How to get 30 is important.

[C++/Java/Python] O(30N) - LeetCode Discuss

“Ok, got it. For anyone still wondering….

B[0][i] >= B[1][i] >= ... >= B[I][I]
The sequence is monotone, so for subsequent change, it must have more no of 1s (Since we're using Bitwise OR, so once a bit is set, it can never be unset on adding subsequent no) than the previous. So max is 30.”

https://leetcode.com/problems/bitwise-ors-of-subarrays/discuss/165881/C++JavaPython-O(30N)/172068

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        res, cur = set(), set()
        for i in A:
            cur = {i | j for j in cur}
            cur.add(i)
            res |= cur
        return len(res)