0792MediumArrayHash TableGreedySorting

Recover the Base Readings

Tracked in this browser only

Trains the technique from

LeetCode 2007Find Original Array From Doubled Array

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 measures a batch of samples. For every sample the rig prints two rows on one sheet: the sample's base reading, and a second row holding exactly twice that base reading. A base reading of 0 therefore prints two rows of 0. The sheet then went through a shredder and was reassembled in some arbitrary order, giving the list sheet.

Work out the base readings the rig measured and return them in ascending order. If no set of base readings could have printed sheet — including the case where sheet holds an odd number of rows — return an empty list.

Examples

Example 1

Input: sheet = [6, 3, 1, 2]
Output: [1, 3]

Base reading 1 printed the rows 1 and 2, and base reading 3 printed the rows 3 and 6. Together those four rows are exactly the sheet, so the base readings are reported ascending.

Example 2

Input: sheet = [0, 0, 3, 6]
Output: [0, 3]

Base reading 0 printed two rows of 0, and base reading 3 printed the rows 3 and 6.

Example 3

Input: sheet = [3, 3, 6, 6, 12, 12]
Output: []

There is no set of three base readings whose printed rows come to this sheet, so the empty list is returned.

Constraints

1 <= sheet.length <= 10^5
0 <= sheet[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 recover_base_readings(sheet: list[int]) -> list[int]:

Java

public int[] recoverBaseReadings(int[] sheet)

The intended approach

Time O(n log n) for n rows: the tally is linear and the distinct readings are sorted once.Space O(n) for the tally plus the returned readings.

Tally how often each reading appears, then work through the distinct readings in ascending order. Nothing smaller is left when a reading is reached, so every remaining copy of it has to be a base reading, and each one claims one copy of twice its value from the tally; if the tally is short, the sheet cannot be explained. Zero is handled on its own because its double is itself, so an odd number of zeros is impossible and an even number contributes half that many zero base readings. Walking the distinct readings upward makes the collected answer ascending already.

Pythonentry point: recover_base_readings

def recover_base_readings(sheet):
    n = len(sheet)
    if n % 2:
        return []
    tally = {}
    for v in sheet:
        tally[v] = tally.get(v, 0) + 1
    bases = []
    # smallest reading first: whatever is left of it can only be a base
    for v in sorted(tally):
        c = tally[v]
        if c == 0:
            continue
        if v == 0:
            if c % 2:
                return []
            bases.extend([0] * (c // 2))
            tally[0] = 0
            continue
        if tally.get(2 * v, 0) < c:
            return []
        tally[2 * v] -= c
        tally[v] = 0
        bases.extend([v] * c)
    return bases

The obvious version

Search over pairings instead of reasoning about order: repeatedly take the first unpaired row, try every other unpaired row that is either double it or half it, and recurse. Every complete pairing yields a candidate list of base readings, and the smallest such list is returned; if no pairing completes, the sheet cannot be explained. Exponential.

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_recover_base_readings(sheet):
    n = len(sheet)
    if n % 2:
        return []
    vals = list(sheet)
    used = [False] * n
    best = [None]

    def walk(bases):
        if 2 * len(bases) == n:
            cand = sorted(bases)
            if best[0] is None or cand < best[0]:
                best[0] = cand
            return
        i = 0
        while used[i]:
            i += 1
        used[i] = True
        for j in range(i + 1, n):
            if used[j]:
                continue
            used[j] = True
            if vals[j] == 2 * vals[i]:
                walk(bases + [vals[i]])
            elif vals[i] == 2 * vals[j]:
                walk(bases + [vals[j]])
            used[j] = False
        used[i] = False

    walk([])
    return best[0] if best[0] is not None else []

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