1118MediumArrayBacktrackingBit ManipulationEnumeration

Groups of Relays That Reach the Widest

Tracked in this browser only

Trains the technique from

LeetCode 2044Count Number of Maximum Bitwise-OR Subsets

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 rack holds relays, and relays[i] is a whole number saying which lines relay i closes: the lines are the bits of that number.

Picking a group of one or more relays closes every line that any relay in the group closes, so the group's reach is the bitwise OR of the numbers in it.

Let the widest reach be the largest reach any group can manage. Return how many groups reach it. Two groups count apart when they use different relays, even if their reaches match.

Examples

Example 1

Input: relays = [1, 1]
Output: 3

Both relays close the same single line, so the widest reach is that line and all three non-empty groups manage it.

Example 2

Input: relays = [4, 1, 2, 3]
Output: 5

Together the relays close three lines. Only one relay closes the third of them, so it belongs to every group that reaches the widest, and the other three relays supply the remaining two lines in five ways.

Example 3

Input: relays = [1, 2, 4, 8]
Output: 1

Each relay closes a line no other relay touches, so only the group holding all four reaches the widest.

Constraints

1 <= relays.length <= 16
1 <= relays[i] <= 10^5

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 count_max_or_subsets(relays: list[int]) -> int:

Java

public int countMaxOrSubsets(int[] relays)

The intended approach

Time O(n * r) for n relays and r distinct reaches.Space O(r) for the tally.

The widest reach is the reach of every relay together, because adding a relay to a group can only close more lines and never fewer. So one pass settles what the target is. Counting the groups that hit it needs no walk over all the groups. Carry a tally of how many groups so far reach each value, starting with the empty group reaching nothing. Bringing in one more relay leaves every existing group untouched and also creates a copy of each with that relay added, whose reach is the old reach with the relay's lines folded in. So the new tally is the old tally plus, for each recorded reach, that many groups landing on the folded value. Distinct reaches never outnumber the groups and in practice collapse hard, which is what makes this cheaper than listing groups. Every relay closes at least one line, so the widest reach is never nothing and the empty group can never be miscounted.

Pythonentry point: count_max_or_subsets

def count_max_or_subsets(relays):
    widest = 0
    for value in relays:
        widest |= value
    tally = {0: 1}
    for value in relays:
        step = dict(tally)
        for reach in tally:
            joined = reach | value
            step[joined] = step.get(joined, 0) + tally[reach]
        tally = step
    return tally.get(widest, 0)

The obvious version

List every group as a bit pattern over the relays, fold its numbers together with OR, and count the ones whose reach matches the widest. Costs two to the power of the relay count times the relay count.

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_count_max_or_subsets(relays):
    n = len(relays)
    widest = 0
    for value in relays:
        widest |= value
    total = 0
    for mask in range(1, 1 << n):
        reach = 0
        for i in range(n):
            if mask >> i & 1:
                reach |= relays[i]
        if reach == widest:
            total += 1
    return total

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