Skip to content

898. Bitwise ORs of Subarrays 👍

  • Time: $O(n\log\max(\texttt{arr}))$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  int subarrayBitwiseORs(vector<int>& arr) {
    vector<int> s;
    int l = 0;

    for (const int a : arr) {
      const int r = s.size();
      s.push_back(a);
      // s[l..r) are values generated in the previous iteration
      for (int i = l; i < r; ++i)
        if (s.back() != (s[i] | a))
          s.push_back(s[i] | a);
      l = r;
    }

    return unordered_set<int>(s.begin(), s.end()).size();
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
  public int subarrayBitwiseORs(int[] arr) {
    List<Integer> s = new ArrayList<>();
    int l = 0;

    for (final int a : arr) {
      final int r = s.size();
      s.add(a);
      // s[l..r) are values generated in the previous iteration
      for (int i = l; i < r; ++i)
        if (s.get(s.size() - 1) != (s.get(i) | a))
          s.add(s.get(i) | a);
      l = r;
    }

    return new HashSet<>(s).size();
  }
}