Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

898. Bitwise ORs of Subarrays

Time: $O(n\log\max(\texttt{arr}))$

Space: $O(n)$

			


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 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>(begin(s), end(s)).size();
  }
};




			


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 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();
  }
}