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 Sam K., 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.

More Bloomberg coding interview questions

See all Bloomberg problems →

Companies that also ask Single Number