Skip to main content

10. Single Number

easyAsked at Chime

Given a non-empty array where every element appears twice except one, find that single element in O(n) time and O(1) space.

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

Problem

You are given a non-empty array of integers nums where every element appears twice except for one. Find the single element that appears only once. Your solution must run in linear time and use constant extra space.

Constraints

  • 1 <= nums.length <= 3 * 10^4
  • -3 * 10^4 <= nums[i] <= 3 * 10^4
  • Every element appears twice except for one.

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)
const counts = new Map();
for (const n of nums) counts.set(n, (counts.get(n) || 0) + 1);
for (const [k, v] of counts) if (v === 1) return k;

Tradeoff:

2. XOR all elements

XOR is commutative and self-cancelling; a^a=0 and a^0=a, so XORing all elements leaves the unique value.

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

Tradeoff:

Chime-specific tips

Chime favors the XOR trick here because their fraud-heuristics pipelines reward candidates who reach for bitwise tricks to deduplicate transaction-event streams in constant memory.

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 Chime interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →