Domain 2MediumMEDIUM

Bitwise ORs of Subarrays

Calculate unique bitwise OR sums for all contiguous subarrays using a sliding window set approach bounded by bit width.

Domain: medium•Updated: 2026-09-03
#sliding window#set

Problem Breakdown

We are given an array arr of non-negative integers. We need to consider every possible contiguous subarray within this input. For each subarray, we calculate the bitwise OR of all its elements. The goal is to return the count of unique values produced by these operations across all valid subarrays.

  • Inputs: A list arr containing non-negative integers (0≤nums[i]≤1090 \le nums[i] \le 10^9).
  • Outputs: An integer representing the number of distinct bitwise OR results found among all contiguous subarrays.
  • Constraints & Edge Cases:
    • Array length up to 5⋅1045 \cdot 10^4. This rules out any solution with quadratic time complexity (O(N2)O(N^2)) or worse, as it would exceed typical execution limits (approx. 2.5×1092.5 \times 10^9 operations).
    • Values are non-negative and fit within standard integer types; bitwise OR does not cause overflow in the sense of wrapping around negative numbers here since Python handles large integers automatically, but logically we care about bit positions up to ≈30\approx 30.
    • Duplicates: The problem explicitly asks for unique results. If multiple subarrays yield the same value (e.g., [1] and another [1]), it counts as one result in our final tally.

Intuition

A naive approach would be to iterate through every starting index i, then every ending index j >= i, compute the OR sum for each subarray, store results in a set, and return its size.

  • Brute Force Complexity: There are O(N2)O(N^2) subarrays. Computing an OR sum naively takes time proportional to length, leading to O(N3)O(N^3). Even if we maintain running sums (incremental update), it remains O(N2)O(N^2) states with a set lookup overhead. Given N=50,000N=50,000, N2N^2 is roughly 2.5 billion operations, which will time out.

Key Insight: The bitwise OR operation has two critical properties:

  1. Monotonicity (Idempotence): Adding more elements to a subarray can only set new bits; it never unsets existing ones. x | y is always ≥x\ge x.
  2. Bit Width Limitation: Since the maximum value in the array is 10910^9 (<230< 2^{30}), there are at most ~30 distinct bit positions that can be set.

For any specific ending index, how many distinct OR sums exist for subarrays ending there? Consider a fixed end position j. As we extend the start position backwards from j to i, the running OR sum changes only when new bits are encountered. Since there are at most 30 bits in an integer (for 10910^9), any sequence of subarrays ending at index j can produce at most ~30 unique values before they stabilize or repeat patterns relative to bit masks.

This means the set of active OR sums ending at current position is small and bounded by the number of bits (W≈32W \approx 32). We don’t need to store all O(N2)O(N^2) subarray results; we only track unique values ending at each step, which keeps our working memory constant relative to bit width.

Approach

  1. Initialize a global set unique_results to collect every distinct OR value found across the entire array traversal.
  2. Maintain a sliding window of active sums ending at the current index, stored in a variable (e.g., current_sums).
  3. Iterate through each number num in the input array:
    • Create a new set for this step (next_sums) initialized with just {num} (representing the subarray of length 1 starting at current index).
    • For every value val stored in current_sums from the previous iteration, compute val | num. Add these to next_sums. This represents extending all valid subarrays ending previously by one more element.
    • Update unique_results with all values currently generated (from both new single-element and extended subarrays).
    • Replace current_sums with next_sums.
  4. Return the size of unique_results.

Complexity Analysis

  • Time Complexity: O(N⋅W)O(N \cdot W), where NN is array length and WW is number of bits (approx 30). In each iteration over NN, we process a set whose size never exceeds WW. Thus, it effectively behaves as linear time relative to input size for practical purposes.
  • Space Complexity:
    • Auxiliary space: O(W)O(W) for the current_sums and next_sums sets at any given step (bounded by bit width).
    • Storage space: O(U)O(U) where UU is the number of unique results found. In worst case, this could be bounded by min⁡(N2/2+N,230)\min(N^2/2 + N, 2^{30}), but practically fits within memory limits for standard integer ranges given constraints on array length and value magnitude.

Solution

class Solution:
    def subarrayBitwiseORs(self, arr):
        """
        Calculates the number of unique bitwise OR results from all contiguous 
        subarrays in the input array using a sliding window set approach.
        
        :type arr: List[int]
        :rtype: int
        """
        # Set to store every distinct result found across all iterations
        unique_results = set()
        
        # Handle edge case for empty list if constraints allowed it, 
        # though problem guarantees 1 <= nums.length.
        if not arr:
            return 0
            
        # This set tracks all possible OR sums ending at the previous index
        current_sums = {arr[0]} 
        unique_results.add(arr[0])

        for i in range(1, len(arr)):
            num = arr[i]
            
            # Start a new window with just the element itself (subarray of length 1)
            next_sums = {num}
            
            # Extend all subarrays ending at previous index by OR-ing with current number
            for val in current_sums:
                next_sums.add(val | num)
            
            # Add new unique results to our global collection
            unique_results.update(next_sums)
            
            # Move the window forward; discard old sums, keep only those ending at i
            current_sums = next_sums
            
        return len(unique_results)

# Example usage for local testing (not part of class submission):
if __name__ == "__main__":
    sol = Solution()
    print(sol.subarrayBitwiseORs([0]))       # Output: 1
    print(sol.subarrayBitwiseORs([1, 1, 2])) # Output: 3
    print(sol.subarrayBitwiseORs([1, 2, 4])) # Output: 6

Edge Cases Handled

  • Single Element Array: The loop range logic handles len(arr) == 1 correctly by initializing with the first element and skipping the main iteration if length is 1 (though my code above iterates from index 1, so for len=1 it returns immediately after init). Correction: My code initializes current_sums = {arr[0]} then loops range(1, N). If N=1, loop doesn’t run. Returns len(unique_results) which is 1. Correct.
  • All Zeros: ORing zeros results in zero. The set will contain {0}, size remains 1 (or grows if mixed with non-zeros). Handled correctly by bitwise logic.
  • Large Values (10910^9): Python handles arbitrary precision integers, so overflow is not an issue; the bit width constraint naturally limits complexity regardless of specific value magnitude as long as it fits in standard integer representation.
  • Duplicate Subarray Results: The unique_results set automatically deduplicates values generated from different subarrays (e.g., [1] | [2] vs another path yielding same sum).