Show problems as
Classic problem #540MediumArrayBinary Search

Single Element in a Sorted Array

Real-world version: Unmatched Component Serial
Tracked in this browser only
Read Single Element in a Sorted Array on LeetCode(opens in a new tab)

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

A repair depot stocks components in matched pairs, one for the machine and one held as a spare, and both members of a pair carry the same serial. The stock sheet serials lists the serial of every component on the shelf in non-decreasing order.

One component arrived without its twin, so exactly one serial appears once on the sheet while every other serial appears twice. Return the serial of that unmatched component.

The sheet can be very long, so your routine must finish in O(log n) time and use O(1) extra space.

Examples

Example 1

Input
serials = [4, 4, 12, 12, 19, 19, 23]
Output
23

Serials 4, 12 and 19 each sit on the shelf twice, and 23 sits at the far end on its own.

Example 2

Input
serials = [6, 11, 11, 30, 30]
Output
6

The unmatched component opens the sheet, so every pair after it starts at an odd position.

Example 3

Input
serials = [2, 2, 7, 15, 15]
Output
7

The pair 2, 2 sits before the loose component and the pair 15, 15 sits after it.

Constraints

  • 1 <= serials.length <= 10^5
  • serials.length is odd
  • 0 <= serials[i] <= 10^5
  • serials is sorted in non-decreasing order
  • Every serial appears exactly twice except one, which appears 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 unmatched_serial(serials: list[int]) -> int:
Java
public int unmatchedSerial(int[] serials)

More on the same topics