Code Implementation

class Solution:
    def subarrayBitwiseORs(self, arr):
        res = set()
        curr = set()
        for x in arr:
            curr = {x | y for y in curr} | {x}
            res |= curr
        return len(res)
      

class Solution {
public:
    int subarrayBitwiseORs(vector<int>& arr) {
        unordered_set<int> res;
        unordered_set<int> curr;
        for (int x : arr) {
            unordered_set<int> next;
            next.insert(x);
            for (int y : curr) {
                next.insert(x | y);
            }
            curr = next;
            res.insert(curr.begin(), curr.end());
        }
        return res.size();
    }
};
      

class Solution {
    public int subarrayBitwiseORs(int[] arr) {
        Set<Integer> res = new HashSet<>();
        Set<Integer> curr = new HashSet<>();
        for (int x : arr) {
            Set<Integer> next = new HashSet<>();
            next.add(x);
            for (int y : curr) {
                next.add(x | y);
            }
            curr = next;
            res.addAll(curr);
        }
        return res.size();
    }
}
      

var subarrayBitwiseORs = function(arr) {
    let res = new Set();
    let curr = new Set();
    for (let x of arr) {
        let next = new Set([x]);
        for (let y of curr) {
            next.add(x | y);
        }
        curr = next;
        for (let val of curr) res.add(val);
    }
    return res.size;
};
      

Problem Description

Given an array of integers arr, your task is to find out how many different results can be obtained by taking the bitwise OR of every possible contiguous subarray of arr.

In other words, for every subarray (a continuous segment) of arr, compute the bitwise OR of its elements, and count how many unique values appear among all these results.

• Each subarray must be contiguous.
• Each result must be counted only once, even if it appears for multiple subarrays.
• Return the total number of unique bitwise OR results.

Thought Process

The straightforward way to solve this problem is to consider every possible subarray, compute its bitwise OR, and collect all unique results. However, since there are O(n²) subarrays in an array of length n, this brute-force approach would be too slow for large arrays.

To optimize, we need to avoid redundant computations. Notably, the bitwise OR operation is associative and accumulative: OR-ing more numbers together can only set more bits, never unset them. This property allows us to efficiently track the results for all subarrays ending at each position, and build upon previous computations rather than recomputing from scratch.

By using sets to store results for subarrays ending at each index, and updating these sets as we iterate through the array, we can avoid unnecessary recalculations and ensure we only compute each unique OR result once.

Solution Approach

Let's break down the optimized algorithm step by step:

1. Initialize a set res: This set will store all unique bitwise OR results across all subarrays.
2. Initialize a set curr: This set will store all the possible bitwise OR results for subarrays ending at the current position in the array.
3. Iterate through each element x in arr:
   • For each existing value y in curr, compute x | y (the bitwise OR of x and y).
   • Also, start a new subarray with just x (so include x itself).
   • Store all these results in a new set next.
   • Update curr to be next (the set of all ORs for subarrays ending at this x).
   • Add all values in curr to res (the global set of unique results).
4. Return the size of res: This is the total number of unique bitwise OR results.

We use sets because they efficiently handle duplicate values, ensuring that each unique OR result is only counted once.

Example Walkthrough

Let's walk through a sample input: arr = [1, 2, 4]

• Step 1: Start with res = {}, curr = {}
• First element (1):
  • curr = {1} (start new subarray)
  • res = {1}
• Second element (2):
  • From previous curr = {1}, calculate 2 | 1 = 3
  • Also, start new subarray: 2
  • curr = {2, 3}
  • res = {1, 2, 3}
• Third element (4):
  • From previous curr = {2, 3}:
  • 4 | 2 = 6
  • 4 | 3 = 7
  • Also, start new subarray: 4
  • curr = {4, 6, 7}
  • res = {1, 2, 3, 4, 6, 7}
• Final answer: res contains 6 unique OR results: 1, 2, 3, 4, 6, 7.

Time and Space Complexity

Brute-force approach:

• There are O(n²) subarrays in an array of length n.
• Computing the OR for each subarray can take up to O(n) time (if we recompute from scratch).
• Total time complexity: O(n³), which is too slow for large n.

• At each step, the number of unique OR values for subarrays ending at position i is at most 32 (since integers are 32 bits), but in practice, usually much less.
• For each element, we combine with all values in curr (which can be up to 32), so the per-step work is O(32) = O(1).
• Total time complexity: O(n * k), where k is the number of unique OR results (bounded by 32 * n in the worst case, but much less in practice).
• Space complexity: O(k), for storing the unique results in the set.

This makes the optimized solution efficient enough for typical input sizes in coding interviews and LeetCode.

Summary

By leveraging the properties of the bitwise OR operation and using sets to efficiently track unique results, we avoid redundant computations and reduce the problem from a cubic to nearly linear time solution. The key insight is that each subarray's OR result can be built from previous ones, and that the number of unique ORs is manageable due to the nature of bitwise operations. This results in a clean, elegant, and highly efficient solution to the problem.