1057MediumArrayDynamic ProgrammingBit Manipulation

How Many Different Merged Masks Appear

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def subarray_bitwise_o_rs(masks: list[int]) -> int:

Java

public int subarrayBitwiseORs(int[] masks)

The intended approach

Time O(n * B) for n masks and B bits, since the carried collection stays about B long.Space O(n * B) at worst for everything gathered.

Take the runs ending at each position in turn. The merged masks of the runs ending here are exactly the mask here, merged with each of the merged masks of the runs ending one place back. So carry that collection along, rebuilding it at each step from the previous one and the mask in hand, and gather everything ever seen. That collection stays small. Extending a run only ever adds bits, never removes them, so along the runs ending at a fixed position the merged masks form a chain where each has all the bits of the one before. A chain of masks under thirty bits can only be thirty or so long, so each step handles a few dozen values however long the list is. The size of everything gathered is the answer.

Pythonentry point: subarray_bitwise_o_rs

def subarray_bitwise_o_rs(masks):
    seen = set()
    ending = set()
    for mask in masks:
        nxt = set()
        nxt.add(mask)
        for before in ending:
            nxt.add(before | mask)
        ending = nxt
        for value in ending:
            seen.add(value)
    return len(seen)

The obvious version

Take every run outright: for each starting place, walk forward merging as you go and gather each merged mask met along the way. The size of everything gathered is the answer. Costs the list's length squared rather than a carried collection a few dozen long.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_subarray_bitwise_o_rs(masks):
    n = len(masks)
    seen = set()
    for start in range(n):
        merged = 0
        for end in range(start, n):
            merged |= masks[end]
            seen.add(merged)
    return len(seen)

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in