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 inputInput: 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