Question

898. Bitwise ORs of Subarrays

中文文档

Description

Given an integer array arr, return _the number of distinct bitwise ORs of all the non-empty subarrays of_ arr.

The bitwise OR of a subarray is the bitwise OR of each integer in the subarray. The bitwise OR of a subarray of one integer is that integer.

A subarray is a contiguous non-empty sequence of elements within an array.

 

Example 1:

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

Example 2:

Input: arr = [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: arr = [1,2,4]
Output: 6
Explanation: The possible results are 1, 2, 3, 4, 6, and 7.

 

Constraints:

• 1 <= arr.length <= 5 * 104
• 0 <= arr[i] <= 109

Solutions

Solution 1: Hash Table

The problem asks for the number of unique bitwise OR operations results of subarrays. If we enumerate the end position $i$ of the subarray, the number of bitwise OR operations results of the subarray ending at $i-1$ does not exceed $32$. This is because the bitwise OR operation is a monotonically increasing operation.

Therefore, we use a hash table $ans$ to record all the results of the bitwise OR operations of subarrays, and a hash table $s$ to record the results of the bitwise OR operations of subarrays ending with the current element. Initially, $s$ only contains one element $0$.

Next, we enumerate the end position $i$ of the subarray. The result of the bitwise OR operation of the subarray ending at $i$ is the set of results of the bitwise OR operation of the subarray ending at $i-1$ and $a[i]$, plus $a[i]$ itself. We use a hash table $t$ to record the results of the bitwise OR operation of the subarray ending at $i$, then we update $s = t$, and add all elements in $t$ to $ans$.

Finally, we return the number of elements in the hash table $ans$.

The time complexity is $O(n \times \log M)$, and the space complexity is $O(n \times \log M)$. Here, $n$ and $M$ are the length of the array and the maximum value in the array, respectively.

class Solution:
  def subarrayBitwiseORs(self, arr: List[int]) -> int:
    s = {0}
    ans = set()
    for x in arr:
      s = {x | y for y in s} | {x}
      ans |= s
    return len(ans)

class Solution {
  public int subarrayBitwiseORs(int[] arr) {
    Set<Integer> s = new HashSet<>();
    s.add(0);
    Set<Integer> ans = new HashSet<>();
    for (int x : arr) {
      Set<Integer> t = new HashSet<>();
      for (int y : s) {
        t.add(x | y);
      }
      t.add(x);
      s = t;
      ans.addAll(s);
    }
    return ans.size();
  }
}

class Solution {
public:
  int subarrayBitwiseORs(vector<int>& arr) {
    unordered_set<int> s{{0}};
    unordered_set<int> ans;
    for (int& x : arr) {
      unordered_set<int> t{{x}};
      for (int y : s) {
        t.insert(x | y);
      }
      s = move(t);
      ans.insert(s.begin(), s.end());
    }
    return ans.size();
  }
};

func subarrayBitwiseORs(arr []int) int {
  ans := map[int]bool{}
  s := map[int]bool{0: true}
  for _, x := range arr {
    t := map[int]bool{x: true}
    for y := range s {
      t[x|y] = true
    }
    s = t
    for y := range s {
      ans[y] = true
    }
  }
  return len(ans)
}

function subarrayBitwiseORs(arr: number[]): number {
  const s: Set<number> = new Set();
  const ans: Set<number> = new Set();
  for (const x of arr) {
    const t: Set<number> = new Set();
    for (const y of s) {
      t.add(x | y);
    }
    t.add(x);
    s.clear();
    for (const y of t) {
      s.add(y);
      ans.add(y);
    }
  }
  return ans.size;
}