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 k
th 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(k1, k), result(k2, 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 k
th 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 inA
. 
Space Complexity: , the size of the answer.
Analysis written by: @awice.