Skip to main content

540. Single Element in a Sorted Array

medium

A sorted array has every element appearing twice except one that appears once. Find it in O(log n) using a parity-aware binary search — or O(n) with XOR.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Return the single element that appears only once. Your solution must run in O(log n) time and O(1) space.

Constraints

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^5

Examples

Example 1

Input
nums = [1,1,2,3,3,4,4,8,8]
Output
2

Example 2

Input
nums = [3,3,7,7,10,11,11]
Output
10

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

XOR over the whole array works in O(n) but the constraints demand O(log n).

Hint 2

Before the singleton, pairs start at even indices: nums[2k] == nums[2k+1]. After the singleton, the pattern shifts: nums[2k] == nums[2k-1] starting from an odd index.

Hint 3

Binary search on the half-line index 'first place where the pattern breaks'. At mid, force mid to be even (mid &= ~1) and check whether nums[mid] == nums[mid + 1].

Solution approach

Reveal approach

Parity-aware binary search. lo = 0, hi = n - 1. While lo < hi: mid = (lo + hi) / 2; if mid is odd, decrement it so we look at an even index. Now compare nums[mid] with nums[mid + 1]. If equal, the pair is intact and the singleton lies in indices > mid + 1 — set lo = mid + 2. If unequal, the singleton lies at index <= mid — set hi = mid. When the loop exits, return nums[lo]. O(log n) time, O(1) space. The invariant: before the singleton, every pair sits at (even, odd) indices; after the singleton, pairs sit at (odd, even). Binary-searching that boundary is the standard log-trick.

Complexity

Time
O(log n)
Space
O(1)

Related patterns

  • binary-search
  • bit-manipulation

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google

Practice these live with InterviewChamp.AI

Drill Single Element in a Sorted Array and Bit Manipulation problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →