Approach 1: Frontier Set
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).
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.
Time Complexity: , where is the length of
A, and is the maximum size of elements in
Space Complexity: , the size of the answer.
Analysis written by: @awice.