13. Single Number

easyAsked at SoFi

Find the element that appears exactly once when every other element appears twice — a classic O(1) space problem SoFi uses to filter out brute-forcers.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

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

Examples

Example 1

Input

[2,2,1]

Output

Example 2

Input

[4,1,2,1,2]

Output

Approaches

1. Brute force hash map

Count occurrences and return the key with count 1 (O(n) space).

Time: O(n)
Space: O(n)

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

Tradeoff:

2. XOR reduce

XOR is associative and commutative; x ^ x = 0 and x ^ 0 = x, so XOR-ing every element leaves the unique one.

Time: O(n)
Space: O(1)

function singleNumber(nums) {
  let result = 0;
  for (const n of nums) {
    result ^= n;
  }
  return result;
}

Tradeoff:

SoFi-specific tips

SoFi values constant-space tricks — reconciling fractional-share trades against settled positions often uses XOR-style aggregations to detect mismatched transaction sequences cheaply.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →