Skip to main content

136. Single Number

easyAsked at IBM

Single Number is IBM's XOR-trick screener. The interviewer is grading whether you reach for the bitwise XOR pattern, articulate why it works (a XOR a = 0, a XOR 0 = a, XOR is commutative), and ship it in O(n) time with O(1) space.

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

Source citations

Public interview reports confirming this problem appears in IBM loops.

  • Glassdoor (2026-Q1)— IBM SWE phone-screen recurring problem (bit manipulation track).
  • LeetCode (2026-Q1)— Top-30 IBM-tagged problem.
  • GeeksforGeeks (2025-12)— Listed in IBM interview-experience archive.

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 toggle

Walk once. For each number, add it if not in the set, otherwise remove it. The single remaining element is the answer.

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.values().next().value;
}

Tradeoff: Correct and O(n) time but O(n) extra space — violates the constraint. Mention it as the obvious answer that the problem explicitly rules out, then move to XOR.

2. Sum twice minus sum once

2 * sum(unique elements) - sum(all elements) = the lonely number.

Time
O(n)
Space
O(n) for the Set
function singleNumberMath(nums) {
  const uniq = new Set(nums);
  let uniqSum = 0;
  for (const n of uniq) uniqSum += n;
  let totalSum = 0;
  for (const n of nums) totalSum += n;
  return 2 * uniqSum - totalSum;
}

Tradeoff: Clever and a useful talking point. Still O(n) space for the unique Set, so it also fails the constraint. The XOR approach is the only true O(1)-space answer.

3. XOR fold (optimal)

XOR all elements together. Pairs cancel (a XOR a = 0); the lonely 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, three-line implementation. The canonical answer. The trick relies on three XOR properties: a XOR a = 0, a XOR 0 = a, and commutativity (order doesn't matter). State all three when explaining.

IBM-specific tips

IBM uses Single Number to filter candidates who know the XOR trick. The hash-set version is the immediate but disqualified answer; the XOR fold is what they want. Always state the three XOR properties out loud — interviewers want to confirm you understand WHY it works, not that you memorized the trick. Bonus points for connecting it to the parity / Hamming-distance literature.

Common mistakes

  • Using `result += n` instead of `result ^= n` — looks similar, completely wrong.
  • Initializing result to nums[0] then XOR-ing from index 1 — works but the cleaner version starts from 0 to handle the single-element case automatically.
  • Trying to use addition/subtraction tricks that overflow on signed 32-bit integers — XOR has no overflow.
  • Claiming XOR works for any 'find the single' problem — it only works when every other element appears EXACTLY twice (or any even count). Doesn't generalize to 'every other appears 3 times' without modification.

Follow-up questions

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

  • Single Number II — every element appears three times except one (LeetCode 137).
  • Single Number III — two elements appear once, everything else twice (LeetCode 260).
  • Missing Number from 0..n with one missing (LeetCode 268) — XOR or sum.
  • Find the duplicate number in [1..n] with one duplicate (LeetCode 287).

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: (1) a XOR a = 0 (any value XOR'd with itself is zero), (2) a XOR 0 = a (XOR with zero is identity), (3) XOR is commutative and associative. So XOR-folding the whole array, every duplicate pair cancels to 0, and the lonely element XOR'd with 0 remains.

Can XOR find the single element if everything else appears 3 times?

Not directly — you need a different technique. The standard answer for the 'every other appears 3 times' variant uses two bitmasks tracking 'seen once' and 'seen twice'. Mention this if the interviewer pivots to Single Number II.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →