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 <= A.length <= 50000
0 <= A[i] <= 10^9
Solution:
[1,2,3,4]
The usual way we solve subarrays is (fix i and run j from i to n-1)
[1][1,2][1,2,3][1,2,3,4]
[2],[2,3][2,3,4]
[3][3,4]
[4]
In this problem it is efficient to arrange subproblems as follows to take full advantage of the partial reulsts to solve other subproblems.
[1]
[1,2][2]
[1,2,3][2,3][3]
[1,2,3,4][2,3,4][3,4][4]
class Solution {
public int subarrayBitwiseORs(int[] A) {
Set<Integer> res = new HashSet();
Set<Integer> prev = new HashSet();
int n = A.length;
for (int i = 0; i < n; i ++) {
Set<Integer> curr = new HashSet();
curr.add(A[i]);
for (int val : prev) {
curr.add(val | A[i]);
}
res.addAll(curr);
prev = curr;
}
return res.size();
}
}