Skip to main content

136. Single Number

easyAsked at Bloomberg

Every element appears twice except one. Find the one. Bloomberg uses this to test the XOR trick — they want the linear-time, constant-space solution, not the hash-set fallback.

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

Source citations

Public interview reports confirming this problem appears in Bloomberg loops.

  • Glassdoor (2026-Q1)— Bloomberg phone-screen reports cite Single Number as the canonical XOR-trick warm-up.
  • Blind (2025-11)— Bloomberg new-grad reports note this for the O(1) space constraint as the actual signal.

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. XOR fold (optimal)

XOR all elements. Pairs cancel; the single survivor is the answer.

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

Tradeoff: The textbook answer. Bloomberg interviewers explicitly want this. Two properties make it work: x ^ x = 0 and x ^ 0 = x. XOR is associative + commutative so order doesn't matter.

2. Hash set (violates constraint)

Track which numbers we've seen; add on first sight, remove on second. What's left is the single.

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

Tradeoff: Works but uses O(n) space — fails the constraint. Bloomberg interviewers want you to NAME this first as the obvious approach, then derive the XOR trick.

Bloomberg-specific tips

Bloomberg interviewers grade specifically on whether you derive XOR aloud. State 'a ^ a = 0, and XOR is associative + commutative, so all the pairs cancel.' That sentence is what they're checking. If you only know the trick by rote, they'll see it.

Common mistakes

  • Reaching for the hash set first without noting the constraint violation.
  • Trying sum-based formula (sum of distinct * 2 - sum of array) — fails on integer overflow / negatives in some languages.
  • Forgetting to initialize result to 0 (you need the identity for XOR).

Follow-up questions

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

  • Single Number II (LC 137) — every element appears three times except one.
  • Single Number III (LC 260) — two elements appear once, rest appear twice.
  • Missing Number (LC 268) — find the missing element in [0, n].

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?

Three identities: x ^ x = 0 (a number XORed with itself cancels), x ^ 0 = x (identity), and XOR is commutative + associative so order doesn't matter. So XORing everything cancels every pair and leaves only the single.

Will Bloomberg ask the three-times variant?

Often as a follow-up. The trick is to think in bits: count each bit mod 3. Practice LC 137 before any Bloomberg loop.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →