Problem Description
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. A subarray is a contiguous non-empty sequence of elements within an array.
Key Insights
- The bitwise OR operation is cumulative and non-decreasing, meaning that as you extend a subarray, the OR value will either stay the same or increase.
- To find distinct OR values, we can keep track of the current OR value as we extend our subarrays.
- Using a set can help easily track unique OR results.
Space and Time Complexity
Time Complexity: O(n)
Space Complexity: O(n)
Solution
To solve this problem, we use a sliding window approach to calculate the bitwise OR of all possible subarrays. We maintain a set to store the distinct OR values. We iterate through the array, extending the current subarray and updating the OR value. If the current OR value is new, we add it to the set.