The Unpaired Value in a Sorted Row

Medium

You are given an array values sorted in non-decreasing order. Every number in it appears exactly twice, except one number that appears exactly once. Find and return that number. A linear pass is easy. Aim for O(log n) time and O(1) extra memory.

Example 1

values=[2, 2, 5, 5, 6, 9, 9] → 6

Every number comes in a pair except 6.

Example 2

values=[0, 4, 4, 7, 7] → 0

The lone number can sit at the very start.

Example 3

values=[13] → 13

Constraints

1 ≤ len(values) ≤ 10⁵
0 ≤ values[i] ≤ 10⁵
values is sorted in non-decreasing order
Exactly one number appears once; all others appear exactly twice

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Binary Search

Similar problems

Find in a Shifted Sorted Array Medium First and Last Copy Medium Find in a Row-Chained Grid Medium Find in a Shifted Array With Repeats Medium Minimum of a Shifted List Medium

Input

values=[2, 2, 5, 5, 6, 9, 9]

Expected

Run checks the first 3 tests in your browser. Submit checks all 115 tests on the server, hidden ones included.