Bitwise ORs of Subarrays

We have an array A of non-negative integers.

For every (contiguous) subarray B = [A[i], A[i+1], ..., A[j]] (with i <= j), we take the bitwise OR of all the elements in B, obtaining a result A[i] | A[i+1] | ... | A[j].

Return the number of possible results. (Results that occur more than once are only counted once in the final answer.)

Example 1:

Input: [0]
Output: 1
Explanation: 
There is only one possible result: 0.

Example 2:

Input: [1,1,2]
Output: 3
Explanation: 
The possible subarrays are [1], [1], [2], [1, 1], [1, 2], [1, 1, 2].
These yield the results 1, 1, 2, 1, 3, 3.
There are 3 unique values, so the answer is 3.

Example 3:

Input: [1,2,4]
Output: 6
Explanation: 
The possible results are 1, 2, 3, 4, 6, and 7.

Note:

1. 1 <= A.length <= 50000

2. 0 <= A[i] <= 10^9

Explaination:

For example, an array is [001, 011, 100, 110, 101] (in binary).

All the subarrays are:

[001]
[001 011] [011]
[001 011 100] [011 100] [100]
[001 011 100 110] [011 100 110] [100 110] [110]
[001 011 100 110 101] [011 100 110 101] [100 110 101] [110 101] [101]

In each line, we add a new number to each array of the previous line.

Calculate the OR operations for each subarray:

001
011 011
111 111 100
111 111 110 110
111 111 111 111 101

There are O(N^2) numbers in total, which is not acceptable.

After removing duplicate numbers in each line, it becomes:

001
011
111 100
111 110
111 101

In each line t, for any two numbers t[i] and t[j] (i < j), t[i] must have more 1s than t[j]. So the length of each line will not exceed 32. So if we remove duplicate numbers, the complexity would not be very large.

The complexity is O(kN), where k is a constant depends on the bitwise length of input numbers. (32 in this problem)

// We can only increase the number of 1s with |
class Solution {
    public int subarrayBitwiseORs(int[] arr) {
        Set<Integer> ans = new HashSet();
        Set<Integer> cur = new HashSet();
        for (int x: arr) {
            Set<Integer> cur2 = new HashSet();
            for (int y: cur)
                cur2.add(x | y);
            cur2.add(x);
            cur = cur2;
            ans.addAll(cur);
        }
        return ans.size();
    }
}