Bitwise ORs of Subarrays — Medium Problem & Solution

Compute the bitwise OR of every contiguous non-empty subarray of arr. Return how many distinct values appear among those results.

Difficulty: Medium
Topics: Arrays, Dynamic Programming, Bit Manipulation
Asked at: Amazon, Google, Meta
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Compute the bitwise OR of every contiguous non-empty subarray of arr.

Return how many distinct values appear among those results.

Example 1

Input: arr = [0]
Output: 1
Explanation: The only subarray ORs to 0.

Example 2

Input: arr = [1,1,2]
Output: 3
Explanation: The distinct results are 1, 2 and 3.

Example 3

Input: arr = [1,2,4]
Output: 6
Explanation: 1, 2, 3, 4, 6 and 7.

Constraints

1 <= arr.length <= 5000
0 <= arr[i] <= 1000000000

How to solve Bitwise ORs of Subarrays

Carry forward the set of ORs of subarrays ending at each position. Extending every one of them by the next element, plus the element alone, gives the next position's set — and that set can only be about 30 values wide, because ORs along a fixed right endpoint form a chain that only ever gains bits.

Approach

Keep cur, the distinct ORs of subarrays ending at the previous index, starting empty.
For each element x, build the next set as {x} ∪ {v | x : v in cur}, deduplicated.
Add every value produced to a global result set.
Return the global set's size.

Why it works

Fixing the right endpoint and extending leftwards produces a non-decreasing chain of ORs, and each strict increase sets at least one new bit — so at most 30 distinct values survive per position. That keeps the total work near O(n · 30) instead of O(n²).

Complexity

Time — O(n · 30)
Space — O(number of distinct ORs)

Pitfalls

Failing to deduplicate cur lets it grow linearly and the solution degrades to O(n²).
Forgetting the single-element subarray {x} misses values that no extension produces.
The global set can hold many values; it is cur that stays small, not the answer.

Reference solution

Python

from typing import List

def subarrayBitwiseORs(arr: List[int]) -> int:
    seen = set()
    cur = set()
    for x in arr:
        cur = {x} | {v | x for v in cur}
        seen |= cur
    return len(seen)

JavaScript

var subarrayBitwiseORs = function(arr) {
    var seen = {}, cur = [];
    for (var i = 0; i < arr.length; i++) {
        var x = arr[i];
        var next = [], local = {};
        var add = function(v) {
            var k = String(v);
            if (local[k] !== true) { local[k] = true; next.push(v); }
            seen[k] = true;
        };
        add(x);
        for (var j = 0; j < cur.length; j++) add(cur[j] | x);
        cur = next;
    }
    return Object.keys(seen).length;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue