Count Distinct Bitwise OR Values of Subarrays

You are given an integer array arr.

For every non-empty contiguous subarray of arr, compute its bitwise OR.

Return the total number of distinct values obtained from all such subarrays.

A subarray is a contiguous sequence of one or more elements within the array.

The bitwise OR of a subarray is the result of applying the OR operation to all elements in that subarray.

Example 1:

Input: arr = [2, 2]

Output: 1

Explanation:

The non-empty subarrays are:

  • [2] → 2
  • [2] → 2
  • [2, 2] → 2

Only one distinct OR value is obtained: {2}.

So, the answer is 1.

Example 2:

Input: arr = [1, 2]

Output: 3

Explanation:

The non-empty subarrays are:

  • [1] → 1
  • [2] → 2
  • [1, 2] → 1 | 2 = 3

Distinct OR values are {1, 2, 3}.

So, the answer is 3.

Now Your Turn!

Pick the correct output for the given input

Input: arr = [1, 3]

Still unsure what the problem is asking ?

Let’s go through a few more examples, step by step, to make it clearer.

Constraints:

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

Hints

Frequently Occurring Doubts

Interview Follow-up Questions

Fun Facts

0
class Solution {
public:
int subarrayBitwiseORs(vector<int>& arr) {
// Your code goes here
}
};
Test Case

Input:

Arr