Skip to main content

898. Bitwise ORs of Subarrays

medium

Count the number of distinct values you can get as the bitwise OR of any contiguous subarray. The hidden bound: at each position, only O(log max) distinct ORs end there.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

We have an array arr of non-negative integers. For every (contiguous) subarray sub = [arr[i], arr[i+1], ..., arr[j]] (with i <= j), we take the bitwise OR of all the elements in sub, obtaining a result arr[i] | arr[i+1] | ... | arr[j]. Return the number of possible results. Results that occur more than once are only counted once in the final answer.

Constraints

  • 1 <= arr.length <= 5 * 10^4
  • 0 <= arr[i] <= 10^9

Examples

Example 1

Input
arr = [0]
Output
1

Explanation: There is only one possible result: 0.

Example 2

Input
arr = [1,1,2]
Output
3

Explanation: The possible subarrays are [1], [1], [2], [1, 1], [1, 2], [1, 1, 2]. These yield the results 1, 1, 2, 1, 3, 3. There are 3 unique values, so the answer is 3.

Example 3

Input
arr = [1,2,4]
Output
6

Explanation: The possible results are 1, 2, 3, 4, 6, and 7.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

There are O(n^2) subarrays. Enumerating each costs O(n^3) — too slow.

Hint 2

Fix the right endpoint j. As you extend leftward, the OR can only gain bits (or stay the same). So at most O(log max_value) distinct ORs end at position j.

Hint 3

Maintain a set of OR values ending at j: cur = {arr[j] | x for x in prev} ∪ {arr[j]}. Add cur to the global answer set.

Solution approach

Reveal approach

Track ORs ending at each position. Maintain a small set cur of all distinct OR values for subarrays ending at the current index. When you advance to index j, the new cur is { arr[j] | x for each x in old cur } union { arr[j] }. Add every element of the new cur to a global answer set. Return |answer|. Why this is efficient: cur grows only when a new bit gets ORed in, and there are at most 30 bits — so |cur| <= 30 throughout. Total work is O(n * log(max_value)). Space is O(n * log(max_value)) for the answer set.

Complexity

Time
O(n log max)
Space
O(n log max)

Related patterns

  • bit-manipulation
  • dynamic-programming

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google

Practice these live with InterviewChamp.AI

Drill Bitwise ORs of Subarrays and Bit Manipulation problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →