Problem statement

https://leetcode.com/problems/bitwise-ors-of-subarrays/

Solution

The idea of solution is the following: let dp(i) be all answers for subarrays which end with i-th element. Then it can be shown, that there is not more than O(log W) of them, where W is the bound for numbers values: we have sequence of embedded subarrays, which has monotonic property: number of ones in binary representation can only increase.

To evaluate dp(i) we look at all solutions for dp(i-1) and OR them with arr[i]. Also we need to consider arr[i] value itself. In the end we intersect all sets we have and give answer.

Complexity

Time and space complexity is O(n log W).

Code

class Solution:
    def subarrayBitwiseORs(self, arr):
        @lru_cache(None)
        def dp(i):
            if i == 0: return tuple([arr[0]])
            return tuple(set(arr[i]|j for j in dp(i-1) + (0,)))
        
        return len({j for i in range(len(arr)) for j in dp(i)})