Skip to main content

12. Single Number

easyAsked at Snap

Find the one integer that appears once when every other appears twice. Snap uses this to test bit-manipulation insight under an O(1)-space constraint.

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

Source citations

Public interview reports confirming this problem appears in Snap loops.

  • LeetCode Discuss (2025)— Reported in Snap onsite as a 'bit-trick' filter problem.
  • Blind (2025-08)— Sometimes paired with Counting Bits for harder follow-ups.

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 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 and return the key with count 1.

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

Tradeoff: Violates the O(1) space constraint Snap explicitly asks for.

2. XOR reduction (optimal)

XOR all elements. Pairs cancel to 0; the lone element survives.

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

Tradeoff: Three-line solution leveraging XOR's self-inverse property — the canonical bit trick.

Snap-specific tips

Snap loves the XOR trick because it shows fluency with bitwise operators — useful in their low-latency image-encoding paths. Articulate the two XOR properties (a^a=0, a^0=a) before coding. Bonus: extend to 'every element appears three times except one' (LC 137).

Common mistakes

  • Forgetting XOR is associative and commutative, leading to unnecessary sorting.
  • Using === to compare instead of XOR.
  • Confusing XOR with OR — OR doesn't cancel pairs.

Follow-up questions

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

  • Single Number II — every element appears 3 times except one (LC 137).
  • Single Number III — exactly two elements appear once (LC 260).
  • Find a missing number from 0..n (LC 268).

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?

Because a ^ a = 0 and a ^ 0 = a. XOR is associative and commutative, so pairs cancel out regardless of order and only the unpaired element remains.

Does this generalize to floats?

Not directly. XOR is a bitwise integer operation. For floats you'd need a different approach (e.g., sum-based with care for precision).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →