Skip to main content

19. Single Number

easyAsked at Reddit

Find the single non-duplicated number in an array where every other number appears twice. Reddit asks this to test bitwise reflexes — the same XOR trick used in their vote-toggle audit (each user vote should appear paired with its undo, except for the active one).

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

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit phone screen, used to gauge bitwise-ops familiarity before vote-fraud follow-ups.

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 count

Count occurrences, return 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 O(n) extra space — fails the constant-space requirement.

2. XOR everything (optimal)

XOR is associative + commutative + a ^ a = 0 + a ^ 0 = a. So XOR of all elements = the unique one.

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

Tradeoff: Constant space. The XOR trick is a Reddit interviewer favorite because it tests whether you remember bitwise identities under pressure.

Reddit-specific tips

Reddit interviewers explicitly grade on remembering the XOR identity. Bonus signal: link to their vote-toggle audit log — vote and unvote events XOR to zero, so any leftover non-zero state in the audit XOR is the active vote.

Common mistakes

  • Forgetting that XOR works because of the constraint (every other element appears exactly twice).
  • Using sum-based tricks (sum - 2*sum(set)) — works but allocates O(n) and overflows.
  • Using a Map and forgetting the constant-space requirement.

Follow-up questions

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

  • Single Number II (LC 137) — every element appears 3 times except one. Use bit counting mod 3.
  • Single Number III (LC 260) — two unique elements. Partition by a bit they differ on.
  • Missing Number (LC 268) — XOR with indices.

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 addition?

XOR is bit-level and doesn't overflow. Addition would work logically (sum - 2*sum(uniques)) but requires extra space and risks overflow.

What if some elements appear 3+ times?

XOR no longer cancels. See LC 137 for the 'three times' variant.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →