Skip to main content

18. Single Number

easyAsked at Vercel

Given an array where every element appears twice except one, find the single one in O(n) time and O(1) space. Vercel asks this for the XOR trick — useful in cache-line dedup and the kind of bit-level micro-optimizations that show up in their edge runtime.

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

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-12)— Vercel screen; XOR expected as the bonus.
  • Blind (2026-Q1)— Reported in Vercel runtime engineer screen.

Problem

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one. You must implement a solution with a linear runtime complexity and use only constant extra space.

Constraints

  • 1 <= nums.length <= 3 * 10^4
  • -3 * 10^4 <= nums[i] <= 3 * 10^4
  • Each element in the array appears twice except for one element which appears only once.

Examples

Example 1

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

Example 2

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

Approaches

1. Hash map count

Count occurrences with a Map; return the key with count 1.

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

Tradeoff: Works but violates the O(1) space constraint. Mention to set up the XOR pivot.

2. XOR accumulator (optimal)

XOR is associative and commutative; a XOR a = 0 and 0 XOR x = x. XOR all elements; pairs cancel; the single element remains.

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

Tradeoff: Three lines, O(1) extra space. The XOR trick generalizes — Vercel may follow up with 'every element appears 3 times except one' (LC 137), which uses a bit-counting variant.

Vercel-specific tips

Vercel uses this to spot the XOR insight. Bonus signal: stating the two properties of XOR (a XOR a = 0, x XOR 0 = x) BEFORE coding. They'll often follow up with 'every element appears 3 times' (LC 137) to see if you generalize cleanly.

Common mistakes

  • Confusing XOR (^) with logical OR (||) or bitwise AND (&) — under pressure this happens.
  • Initializing acc to nums[0] and starting the loop at index 1 — works but loses the elegance of starting at 0.
  • Using a Set with add/delete — works but allocates.

Follow-up questions

An interviewer at Vercel may pivot to one of these next:

  • Every element appears 3 times except one (LC 137).
  • Two single numbers — every element appears twice except two (LC 260).
  • Find the missing number in [0, n] (LC 268) — XOR variant.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why does XOR work?

XOR is associative and commutative, so the order doesn't matter. Every pair contributes a XOR a = 0, leaving only the single element XORed with 0, which is the element itself.

What if some elements appear three times?

Pure XOR fails. You'd need a bit-counter approach: for each bit position, count how many numbers have that bit set, then mod by 3 to find the single number's bit (LC 137).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →