0486MediumArrayBit Manipulation

Unmatched Sensor Drifts

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 calibration rig reads every probe twice during a sweep and appends the probe's signed drift value to one shared log, so a value that belongs to a fully read probe turns up in the log exactly twice. Two probes worked loose partway through the sweep and were read only once, so their drift values turn up exactly once each. No two probes share a drift value.

Given the sweep log drifts, return the two values that appear exactly once. The two may be returned in either order.

The rig has almost no working memory, so use only a constant amount of extra space beyond the log itself, and read the log a constant number of times.

Examples

Example 1

Input: drifts = [12, -5, 9, -5, 12, 7]
Output: [7, 9]

The values -5 and 12 each show up twice, while 9 and 7 each show up once.

Example 2

Input: drifts = [6, 10, 4, 4]
Output: [6, 10]

Only 4 is logged twice, so the loose probes are the ones that reported 6 and 10.

Example 3

Input: drifts = [-31, 18]
Output: [-31, 18]

The log holds nothing but the two single readings, so both of them are loners.

Constraints

2 <= drifts.length <= 3 * 10^4
-2^31 <= drifts[i] <= 2^31 - 1
Every value in drifts appears exactly twice, except for exactly two values that each appear exactly once.

The values you return may be in any order.

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 unmatched_drifts(drifts: list[int]) -> list[int]:

Java

public int[] unmatchedDrifts(int[] drifts)

The intended approach

Time O(n)Space O(1)

Exclusive-or the whole log. Every twice-logged value cancels with its twin, so what survives is the exclusive-or of the two loners, which cannot be zero because the two differ. Isolate its lowest set bit: the two loners fall on opposite sides of that bit, so exclusive-or a second pass restricted to entries carrying that bit yields one loner, and combining it with the full exclusive-or yields the other.

Pythonentry point: unmatched_drifts

def unmatched_drifts(drifts):
    # XOR over the whole sweep cancels every value that shows up twice, leaving
    # the XOR of the two loners. That combined value has at least one set bit,
    # and the two loners disagree on it, so it splits the log into two halves
    # each holding exactly one loner.
    # time O(n), space O(1)
    combined = 0
    for d in drifts:
        combined ^= d
    separator = combined & -combined
    left = 0
    for d in drifts:
        if d & separator:
            left ^= d
    return [left, left ^ combined]

The obvious version

Tally how often each value occurs in a dictionary, then walk the log again and collect the values whose tally is one. Uses memory proportional to the log rather than bit tricks.

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_unmatched_drifts(drifts):
    seen = {}
    for d in drifts:
        seen[d] = seen.get(d, 0) + 1
    out = []
    for d in drifts:
        if seen[d] == 1:
            out.append(d)
    return out

How this problem was checked

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