LeetCode 898 - Bitwise ORs of Subarrays

https://leetcode.com/problems/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

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 $O(N^2)$, where $N$ 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.

• Time Complexity: $O(N \log W)$, where $N$ is the length of A, and $W$ is the maximum size of elements in A.
• Space Complexity: $O(N \log W)$, the size of the answer. 

    public int subarrayBitwiseORs(int[] A) {

        Set<Integer> ans = new HashSet();

        Set<Integer> cur = new HashSet();

        cur.add(0);

        for (int x: A) {

            Set<Integer> cur2 = new HashSet();

            for (int y: cur)

                cur2.add(x | y);

            cur2.add(x);

            cur = cur2;

            ans.addAll(cur);

        }

        return ans.size();

    }

https://leetcode.com/problems/bitwise-ors-of-subarrays/discuss/165881/C%2B%2BJavaPython-O(30N)

Assume B[i][j] = A[i] | A[i+1] | ... | A[j]
Hash set cur stores all wise B[0][i], B[1][i], B[2][i], B[i][i].

When we handle the A[i+1], we want to update cur
So we need operate bitwise OR on all elements in cur.
Also we need to add A[i+1] to cur.

In each turn, we add all elements in cur to res.

Time Complexity:
O(30N)

Normally this part is easy.
But for this problem, time complexity matters a lot.

The solution is straight forward,
while you may worry about the time complexity up to O(N^2)
However, it's not the fact.
This solution has only O(30N)

The reason is that, B[0][i] >= B[1][i] >= ... >= B[i][i].
B[0][i] covers all bits of B[1][i]
B[1][i] covers all bits of B[2][i]
....

There are at most 30 bits for a positive number 0 <= A[i] <= 10^9.
So there are at most 30 different values for B[0][i], B[1][i], B[2][i], ..., B[i][i].
Finally cur.size() <= 30 and res.size() <= 30 * A.length()

In a worst case, A = {1,2,4,8,16,..., 2 ^ 29}
And all B[i][j] are different and res.size() == 30 * A.length()

    public int subarrayBitwiseORs(int[] A) {
        Set<Integer> res = new HashSet<>(), cur = new HashSet<>(), cur2;
        for (Integer i: A) {
            cur2 = new HashSet<>();
            cur2.add(i);
            for (Integer j: cur) cur2.add(i|j);
            res.addAll(cur = cur2);
        }
        return res.size();
    }

https://leetcode.com/problems/bitwise-ors-of-subarrays/discuss/165859/C%2B%2B-O(kN)-solution

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)

X. 

https://leetcode.com/problems/bitwise-ors-of-subarrays/discuss/165933/Python-Dynamic-programming-solution-with-indepth-explanation-of-intuition.

Notice how a lot of these are the same? Once a bit appears in a particular position, it's impossible for it to disappear! What this means, is that we only need to OR the last number with previous ones that are actually unique. This is proportional to the number of bits in the largest number rather than n. That is, it's a lot smaller!

So, for each number in the array, we start with a set containing just that number (because that's what we'd get OR'ing it with itself). We then add all the possibilities we can get by OR'ing the number with results that include the previous number.

    def subarrayBitwiseORs(self, A):
        # Tabulation is a list of sets, one for each number in A. 
        # Each set, at position i, is initialised to containing the element at A[i]
        tabulation = [set([A[i]]) for i in range(len(A))]
        
        # And now we need to go through, updating the sets based on the previous set.
        for i in range(1, len(A)):
            for previous_result in tabulation[i - 1]: 
                tabulation[i].add(A[i] | previous_result)  
        
        # Return the number of unique numbers in the tabulation list.
        return len(set.union(*tabulation)) if len(A) > 0 else 0

https://leetcode.com/problems/bitwise-ors-of-subarrays/discuss/166832/C%2B%2B-simplest-fastest-)-(224-ms)

The idea is similar to the official solution. The important optimization is that we can store the result for step i in a vector instead of a set. Since values are monotone increasing, we can just check if the new value is greater than the last value instead of inserting it in a set.

The second (less important) optimization is to use a single vector (c) instead of two (cur and cur2). We just need to maintain the indexes for the previous step. This allows to insert values into a set (to count the unique ones) in one go.

Follow-up challenge: is it possible to get unique values from n monotone increasing arrays of a fixed size (30 in our case) faster than by using a hash set?

int subarrayBitwiseORs(vector<int>& A) {
  vector<int> c;
  for (auto i = 0, st = 0, en = 0; i < A.size(); ++i, st = en, en = c.size()) {
    c.push_back(A[i]);
    for (auto j = st; j < en; ++j)
      if (c.back() != (c[j] | A[i])) c.push_back(c[j] | A[i]);
  }
  return unordered_set<int>(begin(c), end(c)).size();
}

X.
https://blog.csdn.net/fuxuemingzhu/article/details/83511833
题目不是一般的难啊，如果是普通的DP方法，那么使用二维dp[i][j]表示子数组的起始和结束区间，能做到O(n^2)的时间复杂度，但是题目对时间复杂度要求的很死，必须O(N).

正确的做法也是动态规划，dp[i]表示以A[i]结尾的所有子数组的异或结果，其实是个set。

转移方程式dp[i] = [b | A[i] for b in dp[i - 1]] + A[i]，即以A[i]结尾的所有子数组异或结果等于以A[i-1]结尾的所有子数组异或结果，和当前的A[i]异或，再加上A[i]这个结果。

同时使用一个set保存所有的异或结果。最后返回这个结果set的长度
https://zxi.mytechroad.com/blog/dynamic-programming/leetcode-898-bitwise-ors-of-subarrays/
Solution 2: DP opted

dp[i] := {A[i], A[i] | A[i – 1], A[i] | A[i – 1] | A[i – 2], … , A[i] | A[i – 1] | … | A[0]}, bitwise ors of all subarrays end with A[i].

|dp[i]| <= 32

Proof: all the elements (in the order of above sequence) in dp[i] are monotonically increasing by flipping 0 bits to 1 from A[i].

There are at most 32 0s in A[i]. Thus the size of the set is <= 32.

证明： dp[i] = {A[i], A[i] | A[i – 1], A[i] | A[i – 1] | A[i – 2], … , A[i] | A[i – 1] | … | A[0]}，这个序列单调递增，通过把A[i]中的0变成1。A[i]最多有32个0。所以这个集合的大小 <= 32。

e.g. 举例：Worst Case 最坏情况 A = [8, 4, 2, 1, 0] A[i] = 2^(n-i)。

A[5] = 0，dp[5] = {0, 0 | 1, 0 | 1 | 2, 0 | 1 | 2 | 4, 0 | 1 | 2 | 4 | 8} = {0, 1, 3, 7, 15}.

Time complexity: O(n*log(max(A))) < O(32n)

Space complexity: O(n*log(max(A)) < O(32n)

  public int subarrayBitwiseORs(int[] A) {

    Set<Integer> ans = new HashSet<>();

    Set<Integer> cur = new HashSet<>();

    for (int a : A) {

      Set<Integer> nxt = new HashSet<>();

      nxt.add(a);

      for (int b : cur)

        nxt.add(a | b);

      ans.addAll(nxt);

      cur = nxt;

    }

    return ans.size();

  }

X.
Solution 1: DP (TLE)
dp[i][j] := A[i] | A[i + 1] | … | A[j]

dp[i][j] = dp[i][j – 1] | A[j]

ans = len(set(dp))

Time complexity: O(n^2)

Space complexity: O(n^2) -> O(n)

  int subarrayBitwiseORs(vector<int>& A) {

    int n = A.size();

    vector<vector<int>> dp(n, vector<int>(n));

    unordered_set<int> ans(begin(A), end(A));

    for (int l = 1; l <= n; ++l)

      for (int i = 0; i <= n - l; ++i) {        

        int j = i + l - 1;

        if (l == 1) {

          dp[i][j] = A[i];

          continue;

        }

        dp[i][j] = dp[i][j - 1] | A[j];

        ans.insert(dp[i][j]);

      }

    return ans.size();

  }

  int subarrayBitwiseORs(vector<int>& A) {

    int n = A.size();

    vector<int> dp(A);

    unordered_set<int> ans(begin(A), end(A));

    for (int l = 2; l <= n; ++l)

      for (int i = 0; i <= n - l; ++i)        

        ans.insert(dp[i] |= A[i + l - 1]);

    return ans.size();

  }

X. Divide and Conquer
https://leetcode.com/problems/bitwise-ors-of-subarrays/discuss/165946/Python-Alternative-O(NlogN)-AC-with-Merge
The idea is similar to MergeSort.

1. Split A into Two arrays A1, A2.
2. Merge results from A1 and A2 by calculating OR between TailsubarrayORs of A1 and HeadsubarrayORs of A2.
3. Needs logN calculations and each calculations cost O(N) on average.

def helper(A,cache):
    n = len(A)
    if n==1:
        st, ed, allval = {A[0]}, {A[0]}, A[0]
        cache |= st
        # print cache
        return st,ed, allval
    a_st, a_ed, a_val = helper(A[:n//2],cache)
    b_st, b_ed, b_val = helper(A[n//2:],cache)
    a_st |= {a_val|num for num in b_st}
    b_ed |= {num | b_val for num in a_ed}
    cache |= {n1|n2  for n1 in a_ed for n2 in b_st}
    return a_st, b_ed, a_val|b_val

class Solution(object):
        cache = set()
        helper(A,cache)
        return len(cache)