Skip to main content

136. Single Number

easyAsked at AMD

Find the one element that appears exactly once when every other element appears twice. AMD asks this as a bit-manipulation entry point — XOR is fundamental to parity checking, error detection in memory controllers, and CRC computation in hardware data paths.

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

Source citations

Public interview reports confirming this problem appears in AMD loops.

  • Glassdoor (2026-Q1)— AMD SWE candidates report Single Number as a common bit-manipulation easy used to open hardware-oriented interviews.
  • Blind (2025-11)— AMD prep threads highlight XOR-based problems as higher-frequency at AMD compared to pure SaaS companies.

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

Explanation: 2 XOR 2 = 0; 0 XOR 1 = 1.

Example 2

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

Explanation: XOR all: 4^1^2^1^2 = 4.

Approaches

1. XOR (bit manipulation)

XOR all elements together. Since a ^ a = 0 and a ^ 0 = a, all pairs cancel and the single element remains.

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

Tradeoff: O(n) time, O(1) space. The XOR approach is the canonical bit-manipulation solution. It leverages commutativity and associativity of XOR — order of elements does not matter.

2. Hash Set (reference only)

Add elements to a set; if already present, remove. The remaining element is the single one.

Time
O(n)
Space
O(n)
function singleNumber(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) space — violates the problem's constant-space constraint. Show this as a baseline before presenting XOR.

AMD-specific tips

AMD hardware engineers use XOR constantly: parity bits in ECC memory, CRC polynomials in PCIe/NVMe data paths, and LFSR-based test pattern generation all depend on XOR properties. When presenting this solution, mention the properties explicitly: 'XOR is its own inverse — a ^ a = 0. XOR with 0 is identity — a ^ 0 = a. XOR is commutative and associative so order doesn't matter.' This framing signals hardware-level bit reasoning that AMD interviewers recognize and reward.

Common mistakes

  • Using a hash map with counts instead of XOR — correct but O(n) space, which violates the constraints.
  • Forgetting that XOR is commutative — you don't need to sort; XOR all elements directly.
  • Worrying about negative numbers — XOR works on the two's complement bit representation directly; negatives are fine.
  • Initializing result to nums[0] instead of 0 — initializing to 0 is safe since 0 ^ nums[0] = nums[0].

Follow-up questions

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

  • Single Number II (LC 137) — every element appears three times except one. Requires bit-counting modulo 3.
  • Single Number III (LC 260) — two elements appear once. XOR + find a differing bit to separate them.
  • How is XOR used in hardware parity checking for DRAM ECC?

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?

Because a ^ a = 0 for any value a, all pairs cancel. Whatever remains after XOR-ing the entire array is the element with no pair. XOR's commutativity means order is irrelevant.

Does XOR work with negative numbers?

Yes. Negative numbers in two's complement are just bit patterns. XOR operates bitwise, so the sign bit is handled the same as any other bit.

What if there were three singles instead of one?

XOR alone wouldn't isolate them — you'd need a different approach (frequency counting or bitmask per position modulo 3).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →