Skip to main content

136. Single Number

easyAsked at Goldman Sachs

Every element appears twice except for one. Find the single one in O(1) extra space. Goldman Sachs uses Single Number to test the XOR brainteaser — recognizing that a XOR a = 0 is the entire insight.

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

Source citations

Public interview reports confirming this problem appears in Goldman Sachs loops.

  • Glassdoor (2026-Q1)— Goldman Sachs SWE candidate reports list Single Number as a 'do you know XOR?' brainteaser.
  • LeetCode Discuss (2025-11)— Single Number sits in the top-25 of LeetCode's Goldman Sachs company tag.

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 once.

Examples

Example 1

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

Example 2

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

Example 3

Input
nums = [1]
Output
1

Approaches

1. Hash set / map

Track frequency, return the one with count 1.

Time
O(n)
Space
O(n)
function singleNumberSet(nums) {
  const seen = new Set();
  for (const n of nums) {
    if (seen.has(n)) seen.delete(n);
    else seen.add(n);
  }
  return [...seen][0];
}

Tradeoff: O(n) time but O(n) space — violates the problem's constant-space constraint. Mention it as the obvious starting point, then point out the constraint.

2. XOR all elements (optimal)

XOR has properties: a XOR a = 0, a XOR 0 = a, and XOR is commutative. XOR every element; pairs cancel; the lone one remains.

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

Tradeoff: Single line. O(n) time, O(1) space, satisfies both constraints. The whole problem is whether you remember 'a XOR a = 0' — Goldman tests this specifically.

Goldman Sachs-specific tips

Goldman Sachs interviewers ask this to confirm you know XOR. There is no other 'optimal' answer that meets BOTH constraints (linear time AND constant space). If you reach for hash sets, the interviewer will point out the constant-space constraint and wait for you to think bitwise. Memorize 'a XOR a = 0, a XOR 0 = a, XOR is commutative' and articulate it on the whiteboard before coding.

Common mistakes

  • Suggesting sort-and-find — that's O(n log n) which violates the linear-time constraint.
  • Suggesting hash sets — violates the constant-space constraint.
  • Initializing result to anything other than 0 — XOR has identity 0, not 1 or undefined.

Follow-up questions

An interviewer at Goldman Sachs may pivot to one of these next:

  • Every element appears 3 times except one which appears once (LC #137 Single Number II). Requires bitwise modulo-3 counting per bit.
  • Two elements appear once, everything else twice (LC #260 Single Number III). XOR everything then partition by a differentiating bit.
  • What if you also had to find the appearance counts? (Hash map; not constant space.)

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 here?

Three properties: (a) a XOR a = 0, so any element appearing twice cancels itself; (b) a XOR 0 = a, so the lone element survives when paired with the accumulated zero; (c) XOR is commutative/associative, so the order of operations doesn't matter. XOR-ing every element together leaves only the lone one.

Is XOR the only constant-space O(n) solution?

Effectively yes for this exact problem. Any constant-space solution must combine the elements with an operation that cancels duplicates — XOR is the natural bitwise choice. Arithmetic 'sum minus 2 * sum_of_set' uses O(n) space for the set. So XOR is the canonical answer.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →