Skip to main content

136. Single Number

easyAsked at JPMorgan

Find the one integer that appears once in an array where every other element appears twice. JPMorgan asks this on Software Engineer Programme phone screens to test whether you reach for the XOR trick or default to a hash set — the bit-level insight is the grading signal.

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

Source citations

Public interview reports confirming this problem appears in JPMorgan loops.

  • Glassdoor (2026-Q1)— Recurring JPMorgan SDE phone-screen problem when the interviewer wants to surface bit-manipulation knowledge.
  • LeetCode (2026-Q1)— Tagged JPMorgan on the LeetCode company tag page.
  • Reddit r/cscareerquestions (2025-11)— JPMC SWE-I write-up: 'expected the XOR answer for the constant-space follow-up'.

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 (violates O(1) space)

Walk the array; on first sight add to set, on second sight remove. The set ends with one element.

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][0];
}

Tradeoff: O(n) time but O(n) space — fails the stated constraint. Useful only as a baseline.

2. XOR fold (optimal)

XOR every element together. a XOR a = 0 and 0 XOR x = x, so duplicates cancel and the single survivor is the answer.

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

Tradeoff: One line of state and one operation per element. Provably optimal for the stated constraint — there is no way to do better than O(n) time or O(1) space.

3. Sum-based (only when no integer overflow)

Sum of array minus twice the sum of distinct values equals the single number.

Time
O(n)
Space
O(n) for the Set
function singleNumberSum(nums) {
  return 2 * Array.from(new Set(nums)).reduce((a, b) => a + b, 0) - nums.reduce((a, b) => a + b, 0);
}

Tradeoff: Cute but uses O(n) memory for the Set and breaks under integer overflow in tight-integer languages. The XOR version is strictly better.

JPMorgan-specific tips

JPMorgan interviewers grade two things on this one: (1) you mention the constant-space constraint up front and reject the hash set; (2) you can state why XOR works in plain English — 'XOR is associative, commutative, and self-inverse, so paired duplicates annihilate'. If you can also describe how to extend to LC 137 (one element appears once, others three times) without writing the code, you score a strong-hire.

Common mistakes

  • Reaching for the hash-set version after the O(1) constraint is stated — fails the grading rubric.
  • Initialising the accumulator to nums[0] then iterating from index 0 again (XORs the first element twice).
  • Trying to extend XOR to the 'thrice' variant (LC 137) without thinking through the bit-counting trick.
  • Stating that XOR works 'because of bits' without articulating self-inverse and commutativity.

Follow-up questions

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

  • Single Number II (LC 137) — every element appears three times except one. Use ones/twos bit-counting trick.
  • Single Number III (LC 260) — two elements appear once. Split by a differing bit.
  • What if up to one element could appear an odd number of times greater than 1?
  • Find the missing number from 0..n (LC 268) — sum or XOR trick.

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?

XOR is associative and commutative, so you can XOR the elements in any order. For any value v, v XOR v = 0, and 0 XOR x = x. So pairing up duplicates produces a long product of zeros, leaving only the unique element XOR'd with zero — which is itself.

Does XOR work for the LC 137 variant (each element appears three times except one)?

Not directly. XOR collapses pairs, not triples. The standard trick for LC 137 is two-bit counting: maintain 'ones' and 'twos' variables that together track each bit's count modulo 3. After processing every element, 'ones' holds the unique value.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →