{x}
blog image

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

Solution Explanation: Bitwise ORs of Subarrays

This problem asks us to find the number of distinct bitwise ORs among all non-empty subarrays of a given integer array. A brute-force approach would be computationally expensive. The efficient solution leverages the properties of bitwise OR and uses a set (or hash set) to track unique results.

Approach:

The key observation is that the bitwise OR operation is monotonic. That is, if we have a subarray A, and we extend it by adding an element x, the bitwise OR of the extended subarray (A | x) will be greater than or equal to the bitwise OR of A. This means we don't need to explicitly generate all subarrays.

The algorithm iteratively builds up the set of unique bitwise ORs:

  1. Initialization: Start with an empty set ans to store the unique OR values and a set s initially containing only 0 (to handle cases where the first element is 0).

  2. Iteration: Iterate through the input array arr. For each element x:

    • Create a temporary set t.
    • For each element y in s (the bitwise ORs of subarrays ending at the previous element), calculate x | y and add it to t.
    • Also add x itself to t (representing the subarray containing only x).
    • Add all elements of t to ans.
    • Update s to be t for the next iteration.

  3. Result: After iterating through the entire array, the size of ans (the number of unique elements in ans) represents the number of distinct bitwise ORs of all non-empty subarrays.

Time and Space Complexity:

  • Time Complexity: O(n * k), where n is the length of the input array and k is the number of unique bitwise ORs. In the worst case, k could be O(n), but in practice, it tends to be much smaller due to the nature of the bitwise OR operation. The algorithm's time complexity is dominated by the nested loops in the iteration step.
  • Space Complexity: O(k), where k is the number of unique bitwise ORs. The space is primarily used to store the sets ans and s.

Code Implementation (Python):

class Solution:
    def subarrayBitwiseORs(self, arr: List[int]) -> int:
        ans = set()
        s = {0}  # Initialize with 0 to handle cases with 0s
        for x in arr:
            t = {x | y for y in s} | {x}
            ans |= t
            s = t
        return len(ans)

Code Implementation (Java):

import java.util.HashSet;
import java.util.Set;
 
class Solution {
    public int subarrayBitwiseORs(int[] arr) {
        Set<Integer> ans = new HashSet<>();
        Set<Integer> s = new HashSet<>();
        s.add(0); // Initialize with 0
        for (int x : arr) {
            Set<Integer> t = new HashSet<>();
            for (int y : s) {
                t.add(x | y);
            }
            t.add(x);
            ans.addAll(t);
            s = t;
        }
        return ans.size();
    }
}

The implementations in other languages (C++, Go, TypeScript) follow a similar structure, using their respective set data structures. The core logic remains consistent across all languages.