898. Bitwise ORs of Subarrays LeetCode Solution

In this guide, you will get 898. Bitwise ORs of Subarrays LeetCode Solution with the best time and space complexity. The solution to Bitwise ORs of Subarrays problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Bitwise ORs of Subarrays solution in C++
Bitwise ORs of Subarrays solution in Java
Bitwise ORs of Subarrays solution in Python
Additional Resources

898. Bitwise ORs of Subarrays LeetCode Solution image

Problem Statement of Bitwise ORs of Subarrays

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

Complexity Analysis

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

898. Bitwise ORs of Subarrays LeetCode Solution in C++

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();
  }
};
/* code provided by PROGIEZ */

898. Bitwise ORs of Subarrays LeetCode Solution in Java

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();
  }
}
// code provided by PROGIEZ