Skip to main content

12. Single Number

easyAsked at Intuit

Given an array where every element appears twice except one, find the singleton. Intuit asks this to test whether you recognize XOR as the canonical O(1)-space trick versus reaching for a hash map.

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

Source citations

Public interview reports confirming this problem appears in Intuit loops.

  • Glassdoor (2026-Q1)— Intuit Mint engineering phone screen, follow-up after Two Sum.
  • Reddit r/cscareerquestions (2025-09)— TurboTax candidate noted Single Number as a bit-trick litmus test.

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 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 appears twice except for one element which appears once.

Examples

Example 1

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

Example 2

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

Approaches

1. Hash map count

Count occurrences and return the key with count 1.

Time
O(n)
Space
O(n)
function singleNumber(nums) {
  const count = new Map();
  for (const n of nums) count.set(n, (count.get(n) || 0) + 1);
  for (const [k, v] of count) if (v === 1) return k;
}

Tradeoff: Linear time but O(n) extra space — fails the constant-space requirement.

2. XOR fold (optimal)

XOR has two key properties: x ^ x = 0 and x ^ 0 = x. Folding XOR over the whole array cancels every paired element, leaving only the singleton.

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

Tradeoff: Linear time, constant space. Relies on bitwise XOR being associative + commutative.

Intuit-specific tips

Intuit will press you to articulate why XOR works — the answer is associativity + self-inverse. They also probe variants: what if every element appears 3 times except one (LC 137, needs bitwise counting mod 3)? Bonus signal: discuss whether XOR works for floats (it doesn't directly — you'd need to cast to integer bit-patterns).

Common mistakes

  • Reaching for a hash map and missing the constant-space requirement.
  • Initializing the XOR accumulator to something other than 0.
  • Claiming XOR works on floats without addressing the bit-pattern caveat.

Follow-up questions

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

  • Single Number II — every element appears 3 times except one (LC 137).
  • Single Number III — exactly two elements appear once (LC 260).
  • How would you find the singleton if the array were too large to fit in memory?

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 XOR and not sum or product?

Sum overflows for large inputs; product fails on zeros. XOR is bit-level associative and self-inverse, so paired values cancel without overflow concerns.

Does the order of elements matter?

No. XOR is both associative and commutative, so any traversal order yields the same accumulator.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →