Count Number of Maximum Bitwise-OR Subsets
Real-world version: Groups of Relays That Reach the WidestThe statement here is our own: the same inputs, outputs and technique.
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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def count_max_or_subsets(relays: list[int]) -> int:public int countMaxOrSubsets(int[] relays)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 15 test cases: 15 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's