Skip to main content

8. Single Number

easyAsked at Square

Find the element that appears once when every other element appears twice. Square uses this to test whether you spot the XOR trick — the same bitwise reasoning their payment-checksum and tamper-detect routines rely on.

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

Source citations

Public interview reports confirming this problem appears in Square loops.

  • LeetCode Discuss (2025)— Square Capital phone screen.
  • Reddit r/cscareerquestions (2026)— Square POS team mentioned bit-tricks discussion.

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 O(n) time and O(1) extra space.

Constraints

  • 1 <= nums.length <= 3 * 10^4
  • -3 * 10^4 <= nums[i] <= 3 * 10^4
  • Each element appears twice except for one which appears exactly 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 map count

Count occurrences, then scan for the one 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 violates the O(1) space constraint Square explicitly asks for.

2. XOR fold

XOR all elements. Pairs cancel; the lone element remains.

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

Tradeoff: O(1) space. Relies on XOR's commutative + self-inverse properties (a ^ a = 0, a ^ 0 = a).

Square-specific tips

Square interviewers want you to articulate XOR's algebraic properties explicitly: commutative, associative, self-inverse. The 'pairs cancel' explanation is what they grade for, not the code. Mention that this approach generalizes poorly (single occurrence in stream of any multiplicity needs a different trick) — shows you know its boundary.

Common mistakes

  • Using addition + halving — only works when there's no overflow risk.
  • Returning '!== 0' as truthy without checking the actual single value.
  • Forgetting that 0 is a valid input value — XOR handles it naturally.

Follow-up questions

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

  • Single Number II (LC 137): every other element appears three times.
  • Single Number III (LC 260): two elements appear once.
  • What if elements can be very large (BigInt range)?

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 order doesn't matter. Every paired element XORs with itself to 0, and 0 XOR'd with the singleton is the singleton.

Does it work with negative numbers?

Yes — XOR operates on the 32-bit two's-complement representation. JavaScript bitwise ops convert numbers to int32, which is fine here since constraints stay within int32.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →