Bitwise ORs of Subarrays

https://leetcode.com/problems/bitwise-ors-of-subarrays/description/

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 <= A.length <= 50000

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

Thoughts

不难看出让f[i][j]表示从i到j组成的subarray的值，那么f[i][j+1] = f[i][j] | A[j+1]. 这么做的时间复杂度是O(N^2)。但其实f[0][j]到f[j][j] 结果并没有j个，而是最多31个。因为f[i-1][j]包含了f[i][j]的位数，只可能在它基础上多几个1，而正整数最多只有31个1。因此用一个]集合保存上次循环(j - 1)得出所有的可能性(最多31个)，与A[j] 相or即可，时间复杂度从O(N^2)降到了O(31N).

Code

class Solution {
public:
    int subarrayBitwiseORs(vector<int>& A) {
        unordered_set<int> res, cur, cur2;
        for (int i : A) {
            cur2 = {i};
            for (int j : cur) {
                cur2.insert(i | j);
            }
            cur = cur2;
            for (int j : cur) {
                res.insert(j);
            }
        }

        return res.size();
    }
};

Analysis

时间复杂度O(N). 空间复杂度O(N), 最差情况下cur里每个都是Unique，一共添加了O(N)次.

1. 题目要求是continuous subarray, 漏掉了continuous

2. Continuous subarray的总个数是N^2个，不是指数级个。

3. 结果存在另一个set中。

4. Dp[i][j] (每个I, j往后动以及j, i依次从前到j), 和cur ( the set of results A[i] | ... | A[j] for all i., 对每个j, i依次从前到j) 的区别。前者遍历需要O(N), 后者在这道题里是c。