Unpaired Sock in a Sorted Drawer

MediumBinary Search

Problem

Sock IDs from a laundry drawer are listed in non-decreasing order in socks. Every ID appears exactly twice, side by side, except one ID that appears only once.

Return the unpaired ID in O(log n) time and O(1) space.

Example 1

Input:
socks = [1, 1, 4, 6, 6]
Output:
4

Example 2

Input:
socks = [2, 3, 3]
Output:
2

Example 3

Input:
socks = [8]
Output:
8

Constraints

  • 1 ≤ socks.length ≤ 10^5 (always odd)
  • -10^9 ≤ socks[i] ≤ 10^9
  • Exactly one ID appears once; every other ID appears exactly twice, adjacently.

Hint

Show the first hint

XOR of everything works in O(n). What does the sorted, paired layout give you on top of that?

Walkthrough

How to approach it

01Clarify before coding

  • Are pairs always adjacent? Yes, the list is sorted.
  • Is the length always odd? Yes: 2p + 1.
  • Is XOR acceptable? It is O(n); the requirement is O(log n).

02Brute force

XOR all values (pairs cancel), or step through the list two at a time until a pair does not match.

Cost: O(n) time, O(1) space.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.