0514MediumArrayMathBit Manipulation

Relay Panel Fault Codes

Tracked in this browser only

Trains the technique from

LeetCode 3513Number of Unique XOR Triplets I

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 cabinet holds n relay panels in a row. Panel i carries the stamp stamps[i], and the stamps are exactly the whole numbers from 1 to n, each used once, in some order.

A technician raises a fault code by selecting three panels and combining their stamps with the bitwise XOR operation. The three selections are made independently, so the same panel may be selected two or three times, and the order of the selections does not matter.

Return how many different fault codes can be raised.

Examples

Example 1

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

Selecting the panels stamped 1, 2 and 3 raises the code 0, and selecting the panels stamped 4, 5 and 3 raises the code 2. Over all selections 8 different codes come up.

Example 2

Input: stamps = [7, 5, 6, 8, 2, 1, 4, 3]
Output: 16

Selecting the panels stamped 8, 1 and 7 raises the code 14, and over all selections 16 different codes come up.

Example 3

Input: stamps = [3, 9, 5, 1, 6, 8, 4, 7, 2]
Output: 16

Selecting the panel stamped 5 all three times raises the code 5, and selecting the panels stamped 9, 8 and 2 raises the code 3. In all 16 different codes come up.

Constraints

1 <= stamps.length == n <= 10^5
1 <= stamps[i] <= n
stamps is a permutation of the whole numbers from 1 to n.

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 distinct_fault_codes(stamps: list[int]) -> int:

Java

public int distinctFaultCodes(int[] stamps)

The intended approach

Time O(1): only the number of panels is inspected.Space O(1).

Because the stamps are a permutation of 1 through n, the multiset of stamps is fixed by n alone, so the answer depends only on n. Once three panels are available, every bit pattern narrower than or as wide as n can be assembled, giving 2 raised to the bit width of n distinct codes; the cases n = 1 and n = 2 are too small for that and are answered directly.

Pythonentry point: distinct_fault_codes

def distinct_fault_codes(stamps):
    # The stamps are exactly 1 through n, so the only thing that matters is n.
    # With three panels to combine and repeats allowed, every bit pattern that
    # fits inside the widest stamp becomes reachable once n is at least 3, which
    # is 2 raised to the bit width of n. One and two panels are too few for that
    # and are settled directly.
    # O(1) time, O(1) space.
    n = len(stamps)
    if n == 1:
        return 1
    if n == 2:
        return 2
    return 1 << n.bit_length()

The obvious version

Loop over every selection of three panel positions with repeats allowed, combine the three stamps, drop the results into a set and report its size. O(n^3).

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_distinct_fault_codes(stamps):
    n = len(stamps)
    seen = set()
    for i in range(n):
        for j in range(i, n):
            for k in range(j, n):
                seen.add(stamps[i] ^ stamps[j] ^ stamps[k])
    return len(seen)

How this problem was checked

Reference solution executed against 16 test cases — 16 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