Show problems as
Classic problem #898MediumArrayDynamic ProgrammingBit Manipulation

Bitwise ORs of Subarrays

Real-world version: How Many Different Merged Masks Appear
Tracked in this browser only
Read Bitwise ORs of Subarrays on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A list of channel masks reads masks, each a whole number whose bits say which channels it claims.

Merging a run of neighbouring masks claims every channel any of them claims, so the merged mask has a bit set exactly where at least one mask of the run has it set.

Return how many different merged masks arise over all the runs of one or more neighbouring masks.

Examples

Example 1

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

The single masks give 1, 2 and 3. Merging 1 with 2 gives 3, merging 2 with 3 gives 3, and merging all three gives 3, so only 1, 2 and 3 ever arise.

Example 2

Input
masks = [5, 5, 5]
Output
1

Every mask claims the same channels, so every run merges to the same mask.

Example 3

Input
masks = [0, 0, 0]
Output
1

No mask claims any channel, so every run merges to nothing.

Constraints

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

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def subarray_bitwise_o_rs(masks: list[int]) -> int:
Java
public int subarrayBitwiseORs(int[] masks)

More on the same topics