Bitwise ORs of Subarrays

Medium
740.

Bitwise ORs of Subarrays

Bitwise ORs of Subarrays is a medium coding problem on arrays, dynamic programming and bit manipulation, asked in Amazon, Google and Meta interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {number}
 */
var subarrayBitwiseORs = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Bitwise ORs of Subarrays — Solution in Python, Java & C++

Bitwise ORs of Subarrays solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Bitwise ORs of Subarrays is a medium coding problem on arrays, dynamic programming and bit manipulation, asked in Amazon, Google and Meta interviews.

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

Hints for Bitwise ORs of Subarrays

  1. Hint 1

    Enumerating all subarrays is O(n²) values — too many at the upper limit.

  2. Hint 2

    Track the set of ORs of subarrays ending at the current index.

  3. Hint 3

    That set stays small — at most about 30 values — because each new element can only add bits.

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

  1. Keep cur, the distinct ORs of subarrays ending at the previous index, starting empty.
  2. For each element x, build the next set as {x} ∪ {v | x : v in cur}, deduplicated.
  3. Add every value produced to a global result set.
  4. 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)

Java

public static int subarrayBitwiseORs(int[] arr) {
    Set<Integer> seen = new HashSet<>();
    Set<Integer> cur = new HashSet<>();
    for (int x : arr) {
        Set<Integer> next = new HashSet<>();
        next.add(x);
        for (int v : cur) next.add(v | x);
        cur = next;
        seen.addAll(cur);
    }
    return seen.size();
}

C++

int subarrayBitwiseORs(vector<int>& arr) {
    unordered_set<int> seen, cur;
    for (int x : arr) {
        unordered_set<int> next;
        next.insert(x);
        for (int v : cur) next.insert(v | x);
        cur = next;
        for (int v : cur) seen.insert(v);
    }
    return (int) seen.size();
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming