Show problems as
Classic problem #2007MediumArrayHash TableGreedySorting

Find Original Array From Doubled Array

Real-world version: Recover the Base Readings
Tracked in this browser only
Read Find Original Array From Doubled Array on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def recover_base_readings(sheet: list[int]) -> list[int]:
Java
public int[] recoverBaseReadings(int[] sheet)

More on the same topics