Show problems as
Classic problem #136EasyArrayBit Manipulation

Single Number

Real-world version: The Unpaired Survey Correction
Tracked in this browser only
Read Single Number on LeetCode(opens in a new tab)

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

Two surveyors walk the same stretch of track and file signed elevation corrections in centimetres, negative where the bed sits below the design line. Any correction that truly belongs on the sheet gets filed by both of them, so it shows up on the combined sheet twice. Exactly one correction was filed by a single surveyor, so it shows up there just once.

You are handed the combined sheet as the array corrections, in filing order. Report the value of the correction that shows up only once.

The sheet can run long, so settle it in one sweep over the entries while holding only a fixed amount of extra memory: no tally table, no second copy of the sheet, no reordering.

Examples

Example 1

Input
corrections = [-14, 6, -14, 6, 25]
Output
25

Both -14 and 6 were filed by each surveyor, leaving 25 as the correction only one of them filed.

Example 2

Input
corrections = [0, -9, -9]
Output
0

A correction of zero is a real filing, and here it is the one that shows up a single time.

Example 3

Input
corrections = [-30000]
Output
-30000

A sheet with a single entry can only be the lone filing, so it is reported as is.

Constraints

  • 1 <= corrections.length <= 3 * 10^4
  • -3 * 10^4 <= corrections[i] <= 3 * 10^4
  • Every value on the sheet shows up exactly twice apart from one value, which shows up exactly once.

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 unpaired_correction(corrections: list[int]) -> int:
Java
public int unpairedCorrection(int[] corrections)

More on the same topics