Practice/Microsoft/Leetcode 898. Bitwise ORs of Subarrays

Leetcode 898. Bitwise ORs of Subarrays

CodingMust

Problem

You are given an array of non-negative integers. Your task is to determine how many unique values can be obtained by computing the bitwise OR operation on all possible contiguous subarrays.

A contiguous subarray is any sequence of consecutive elements from the array. For each such subarray, calculate the bitwise OR of all its elements. Count the total number of distinct results across all subarrays.

Requirements

1. Consider every possible non-empty contiguous subarray
2. For each subarray, compute the bitwise OR of all elements in that subarray
3. Return the count of distinct OR values obtained
4. Handle arrays with duplicate elements correctly
5. Account for the special case where the array contains zeros

Constraints

• 1 ≤ arr.length ≤ 50,000
• 0 ≤ arr[i] ≤ 1,000,000,000
• Aim for a solution better than O(n²) time complexity where possible
• Space complexity should be reasonable for the given constraints

Examples

Example 1:

Input: arr = [1, 2, 4] Output: 6 Explanation: The subarrays and their OR values are: [1] → 1 [2] → 2 [4] → 4 [1,2] → 3 [2,4] → 6 [1,2,4] → 7 Distinct values: \{1, 2, 3, 4, 6, 7\} = 6 distinct values

Example 2:

Input: arr = [1, 1, 1] Output: 1 Explanation: All subarrays produce OR value of 1

Example 3:

Input: arr = [0, 1, 1, 2] Output: 3 Explanation: Distinct OR values are 0, 1, 2, and 3