Solution


Approach 1: Frontier Set

Intuition

Let's try to speed up a brute force answer. Evidently, the brute force approach is to calculate every result result(i, j) = A[i] | A[i+1] | ... | A[j]. We can speed this up by taking note of the fact that result(i, j+1) = result(i, j) | A[j+1]. Naively, this approach has time complexity , where is the length of the array.

Actually, this approach can be better than that. At the kth step, say we have all the result(i, k) in some set cur. Then we can find the next cur set (for k -> k+1) by using result(i, k+1) = result(i, k) | A[k+1].

However, the number of unique values in this set cur is at most 32, since the list result(k, k), result(k-1, k), result(k-2, k), ... is monotone increasing, and any subsequent values that are different must have more 1s in it's binary representation (to a maximum of 32 ones).

Algorithm

In the kth step, we'll maintain cur: the set of results A[i] | ... | A[k] for all i. These results will be included in our final answer set.

Complexity Analysis

  • Time Complexity: , where is the length of A, and is the maximum size of elements in A.

  • Space Complexity: , the size of the answer.


Analysis written by: @awice.