Skip to main content

16. Single Number

easyAsked at Indeed

Find the element that appears exactly once in an array where every other element appears twice — the XOR trick appears in Indeed's deduplication pipelines for job listings.

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

Problem

Given a non-empty array of integers nums, every element appears twice except for one. Find that single element. Your solution must run in O(n) time and use only 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 exactly one

Examples

Example 1

Input
nums = [2,2,1]
Output
1

Example 2

Input
nums = [4,1,2,1,2]
Output
4

Approaches

1. Brute force / hash map

Count occurrences with a hash map then return the key 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:

2. XOR bit trick

XOR of identical numbers cancels to 0; XOR-ing all elements leaves only the unique element, achieving O(1) space.

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

Tradeoff:

Indeed-specific tips

Indeed expects the XOR answer immediately; follow up by explaining why a ^ a === 0 and a ^ 0 === a — showing bit-level intuition impresses deduplication pipeline interviewers.

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

Practice these live with InterviewChamp.AI →