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 Sam K., 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

More Bit Manipulation practice problems

See all Bit Manipulation problems →