898: Bitwise ORs of Subarrays

Problem Statement

Given an integer array arr, return the number of distinct bitwise ORs of all non-empty subarrays.

A subarray is a contiguous non-empty sequence of elements within the array. The bitwise OR of a subarray is the bitwise OR of all integers in that subarray.

Key Insight

The solution relies on two crucial observations:

1. The number of distinct OR values for subarrays ending at index i is bounded by O(log(max_value))
2. We can efficiently compute these values using dynamic programming and set operations

Brute Force Approach (TLE)

This approach generates every possible subarray and computes its bitwise OR:

Algorithm Steps

1. Initialize an empty set to store distinct ORs
2. For each starting index i:
   • Initialize current OR to 0
   • For each ending index j from i to end:
     • Compute OR = OR | arr[j]
     • Add OR to the set
3. Return the size of the set

Why It Fails (TLE)

For an array of size n, there are O(n²) subarrays. When n = 50,000, this results in 1.25 billion operations, which is computationally infeasible.

Complexity Analysis

class Solution {
public:
    int subarrayBitwiseORs(vector<int>& arr) {
        unordered_set<int> st;
        int n = arr.size();
        
        for (int i = 0; i < n; i++) {
            int val = 0;
            for (int j = i; j < n; j++) {
                val |= arr[j];
                st.insert(val);
            }
        }
        return st.size();
    }
};

class Solution {
    public int subarrayBitwiseORs(int[] arr) {
        Set<Integer> st = new HashSet<>();
        int n = arr.length;
        
        for (int i = 0; i < n; i++) {
            int val = 0;
            for (int j = i; j < n; j++) {
                val |= arr[j];
                st.add(val);
            }
        }
        return st.size();
    }
}

class Solution:
    def subarrayBitwiseORs(self, arr: List[int]) -> int:
        st = set()
        n = len(arr)
        
        for i in range(n):
            val = 0
            for j in range(i, n):
                val |= arr[j]
                st.add(val)
                
        return len(st)

Optimal Approach: Dynamic Programming with Sets

This approach leverages the insight that the number of distinct OR values for subarrays ending at index i is bounded by O(log(max_value)).

Algorithm Steps

1. Initialize two sets: all_ors (global) and current (ORs ending at current index)
2. For each number in array:
   • Create a new temporary set
   • Add current number to temporary set
   • For each value in previous set, OR with current number and add to temporary set
   • Set current to temporary set
   • Add all values from current to all_ors
3. Return size of all_ors

Why This Works

Each step only considers ORs from the previous index, and the set size is bounded by O(log(max_value)). This reduces time complexity to O(n log max).

Complexity Analysis

Where max is the maximum element in the array (log max is about 30-32 for integers).

class Solution {
public:
    int subarrayBitwiseORs(vector<int>& arr) {
        unordered_set<int> all_ors;
        unordered_set<int> current;
        
        for (int num : arr) {
            unordered_set<int> temp;
            temp.insert(num);
            
            // Combine with previous ORs
            for (int val : current) {
                temp.insert(val | num);
            }
            
            current = temp;
            all_ors.insert(current.begin(), current.end());
        }
        
        return all_ors.size();
    }
};

class Solution {
    public int subarrayBitwiseORs(int[] arr) {
        Set<Integer> all_ors = new HashSet<>();
        Set<Integer> current = new HashSet<>();
        
        for (int num : arr) {
            Set<Integer> temp = new HashSet<>();
            temp.add(num);
            
            // Combine with previous ORs
            for (int val : current) {
                temp.add(val | num);
            }
            
            current = temp;
            all_ors.addAll(current);
        }
        
        return all_ors.size();
    }
}

class Solution:
    def subarrayBitwiseORs(self, arr: List[int]) -> int:
        all_ors = set()
        current = set()
        
        for num in arr:
            # Create new set with current number
            temp = {num}
            # Combine with previous ORs
            for val in current:
                temp.add(val | num)
                
            current = temp
            all_ors |= current  # Union with global set
            
        return len(all_ors)

Optimized Approach: Early Termination

This improvement adds early termination when no new bits are added.

Algorithm Steps

1. Same as optimal approach, but track previous OR value
2. If current set equals previous set, break early

Why This Helps

For arrays with large identical values, we can terminate early once no new OR values are generated.

Complexity Analysis

Same worst-case, but better for certain inputs.

class Solution {
public:
    int subarrayBitwiseORs(vector<int>& arr) {
        unordered_set<int> all_ors;
        unordered_set<int> current;
        int last_size = 0;
        
        for (int num : arr) {
            unordered_set<int> temp;
            temp.insert(num);
            
            for (int val : current) {
                temp.insert(val | num);
            }
            
            // Early termination if no new ORs
            if (temp.size() == last_size && temp == current) {
                continue;
            }
            
            last_size = temp.size();
            current = temp;
            all_ors.insert(current.begin(), current.end());
        }
        
        return all_ors.size();
    }
};

class Solution {
    public int subarrayBitwiseORs(int[] arr) {
        Set<Integer> all_ors = new HashSet<>();
        Set<Integer> current = new HashSet<>();
        int last_size = 0;
        
        for (int num : arr) {
            Set<Integer> temp = new HashSet<>();
            temp.add(num);
            
            for (int val : current) {
                temp.add(val | num);
            }
            
            // Early termination if no new ORs
            if (temp.size() == last_size && temp.equals(current)) {
                continue;
            }
            
            last_size = temp.size();
            current = temp;
            all_ors.addAll(current);
        }
        
        return all_ors.size();
    }
}

class Solution:
    def subarrayBitwiseORs(self, arr: List[int]) -> int:
        all_ors = set()
        current = set()
        last_size = 0
        
        for num in arr:
            temp = {num}
            for val in current:
                temp.add(val | num)
                
            # Early termination if no new ORs
            if len(temp) == last_size and temp == current:
                continue
                
            last_size = len(temp)
            current = temp
            all_ors |= current
            
        return len(all_ors)

Edge Cases and Testing

1. All Zeros

Input: [0,0,0] → Output: 1
Explanation: Only OR value is 0

2. Increasing Powers of Two

Input: [1,2,4,8] → Output: 10
Explanation: OR values: 1,2,4,8,3,5,9,6,10,7,15

3. All Identical Values

Input: [3,3,3] → Output: 1
Explanation: Only OR value is 3

4. Mixed Values

Input: [1,3,5] → Output: 5
Explanation: OR values: 1,3,5,3,7,7

5. Large Input (50,000 elements)

Optimal solution handles in milliseconds
Brute force would take hours

Related Topics Explained

Array

An array is a fundamental data structure consisting of a collection of elements identified by indices. In this problem:

• We work with contiguous subarrays (sequences of adjacent elements)
• Key operations: iteration, indexing, subarray extraction
• Efficient traversal is crucial for optimal solutions

Dynamic Programming

Dynamic programming solves complex problems by breaking them into simpler subproblems and storing their solutions:

• We build solutions incrementally (subarray by subarray)
• Optimal solution uses DP by storing ORs from previous index
• Avoids recomputation through state preservation

Bit Manipulation

Bit manipulation involves direct bit-level operations:

• Bitwise OR combines bits (1 if either operand has 1)
• Key properties: monotonic (ORs only add bits), bounded by word size
• Efficient bit operations enable logarithmic bounds