Skip to main content

14. Single Number

easyAsked at Yelp

Find the unique element in an array where every other element appears twice — Yelp uses this XOR trick to test whether candidates can spot an O(1)-space win before scaling to dedup in review pipelines.

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

Problem

Given a non-empty array of integers where every element appears twice except for one, find that single element. Your solution should run in linear time and use constant extra space.

Constraints

  • 1 <= nums.length <= 3 * 10^4
  • -3 * 10^4 <= nums[i] <= 3 * 10^4
  • Exactly one element appears once; the rest appear twice

Examples

Example 1

Input
nums = [2,2,1]
Output
1

Example 2

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

Approaches

1. Hash count

Count occurrences and return the one with count 1.

Time
O(n)
Space
O(n)
const m = new Map();
for (const x of nums) m.set(x, (m.get(x) || 0) + 1);
for (const [k, v] of m) if (v === 1) return k;

Tradeoff:

2. XOR fold

XOR is its own inverse; folding the array cancels every pair and leaves the single number.

Time
O(n)
Space
O(1)
function singleNumber(nums) {
  let r = 0;
  for (const x of nums) r ^= x;
  return r;
}

Tradeoff:

Yelp-specific tips

Yelp will pivot this to review fraud — be ready to discuss how an XOR-style fingerprint helps detect the single distinct reviewer in a sea of botted duplicate-payload reviews.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Single Number and other Yelp interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →