Skip to main content

136. Single Number

easyAsked at Intel

Every element in nums appears twice except for one, which appears once. Find it. Intel asks because the O(1)-space XOR solution requires you to recognize that XOR is its own inverse — the same algebraic property that drives parity bits, error-correcting codes, and CRC hardware Intel ships in every NIC.

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

Source citations

Public interview reports confirming this problem appears in Intel loops.

  • Glassdoor (2026-Q1)— Intel SWE phone-screen reports cite single-number as a recurring 'find the bit trick' ask.
  • GeeksforGeeks (2025-09)— Intel Interview Experience pages reference the XOR variant explicitly.
  • LeetCode discuss (2025-11)— Intel-tagged in the company-frequency company filter.

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

Example 3

Input
nums = [1]
Output
1

Approaches

1. Hash set (brute / explicit)

Add elements to a set on first sight, remove on second sight. What remains at the end is the single number.

Time
O(n)
Space
O(n)
function singleNumberHash(nums) {
  const seen = new Set();
  for (const x of nums) {
    if (seen.has(x)) seen.delete(x);
    else seen.add(x);
  }
  // Return the only remaining element
  for (const x of seen) return x;
  return -1;
}

Tradeoff: Linear time but linear space. Violates the problem's stated O(1)-space requirement, so it's a starting point — never the final answer.

2. XOR accumulate (optimal)

XOR all elements. Pairs cancel to 0; the singleton survives. Works because XOR is commutative, associative, and self-inverse (a XOR a = 0).

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

Tradeoff: Linear time, constant space, branch-free, cache-friendly. The canonical Intel answer. The hard part is articulating the algebraic invariant — anyone can write the for-loop once they've seen the trick.

Intel-specific tips

Intel interviewers want the algebraic explanation: 'XOR is commutative and associative, so I can reorder the array however I like. Pairs of equal elements XOR to 0, and 0 XOR x = x, so the singleton survives.' Mentioning that this is the same parity-bit logic used in ECC memory or RAID-5 stripes lands as senior hardware-SWE awareness.

Common mistakes

  • Reaching for a hash map and stopping there — violates the O(1)-space constraint stated in the problem.
  • Using sum tricks (`2 * sum(unique) - sum(all)`) — works but requires the same Set, so no space win.
  • Forgetting that XOR doesn't generalize when elements appear three times (LC 137 'Single Number II' needs a different trick — see follow-up).

Follow-up questions

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

  • Single Number II (LC 137) — every element appears three times except one. (Hint: bit-by-bit count mod 3, or two-variable state machine.)
  • Single Number III (LC 260) — exactly two elements appear once; rest appear twice. (Hint: XOR all to get a^b, then partition by any set bit.)
  • What if the array is so large you stream it? (XOR is associative — chunk-and-combine across threads, perfect for SIMD or GPU reductions.)

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 specifically work here and not, say, sum?

Both work mathematically. XOR wins on two counts: (1) it's branch-free at the hardware level — a single XOR-reg op per element — and (2) it doesn't overflow, so it works for the full int range without worrying about 64-bit accumulators.

Could I solve this in O(1) space without XOR?

Sort the array in-place and walk it in pairs — but sort is O(n log n), so you lose the linear-time guarantee. XOR is the only known O(n) time + O(1) space algorithm for this problem.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →