0228MediumArrayBit Manipulation

Once-Logged Drift Reading

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 bench mirrors every drift reading it takes into three separate journals, so the merged dump carries three copies of each reading the bench produced. One reading was keyed in by hand before mirroring was switched on, and that reading sits in the dump on its own.

The merged dump arrives as the integer array readings. Return the reading that occurs only once. Drift may run either side of zero, so a reading can be negative.

Work in time proportional to the length of readings, and hold only a fixed number of extra values while you do it.

Examples

Example 1

Input: readings = [4, 7, 4, 4, 9, 7, 7, 12, 12, 12]
Output: 9

Counting copies: 4 appears three times, 7 appears three times and 12 appears three times, while 9 appears once.

Example 2

Input: readings = [-5, 8, 8, 8]
Output: -5

The dump holds three copies of 8 and a single -5, and the hand-keyed reading is the negative one.

Example 3

Input: readings = [10, 10, 1, 10, 1, 1, -6]
Output: -6

The dump carries three copies of 10 and three copies of 1, and -6 is the reading with a single copy.

Constraints

1 <= readings.length <= 3 * 10^4
-2^31 <= readings[i] <= 2^31 - 1
Every reading in readings occurs exactly three times, except one reading that occurs exactly once

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 once_logged_reading(readings: list[int]) -> int:

Java

public int onceLoggedReading(int[] readings)

The intended approach

Time O(32 * n), that is O(n)Space O(1)

Take the dump one bit column at a time. A reading held in triplicate puts either zero or three set bits into a column, so the column total is a multiple of three except where the lone reading has that bit set, and the answer can be rebuilt column by column. Because the readings are 32-bit signed values while Python integers are unbounded, the bit in position 31 is finally read as a sign and subtracted back out.

Pythonentry point: once_logged_reading

def once_logged_reading(readings):
    single = 0
    for bit in range(32):
        column = 0
        for value in readings:
            column += (value >> bit) & 1
        if column % 3:
            single |= 1 << bit
    if single >> 31 & 1:
        single -= 1 << 32
    return single

The obvious version

Tally every reading in a dictionary, then hand back the key whose tally is one. O(n) time but O(n) extra space, so it ignores the space rule on purpose.

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_once_logged_reading(readings):
    tally = {}
    for value in readings:
        tally[value] = tally.get(value, 0) + 1
    for value, count in tally.items():
        if count == 1:
            return value
    return 0

How this problem was checked

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