Skip to main content

18. Single Number

easyAsked at TripAdvisor

Find the element that appears only once in an array where every other element appears twice.

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

Examples

Example 1

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

Example 2

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

Approaches

1. Hash counts

Tally counts, return the entry with count 1.

Time
O(n)
Space
O(n)
const m = new Map();
for (const x of nums) m.set(x, (m.get(x) || 0) + 1);
for (const [k, v] of m) if (v === 1) return k;

Tradeoff:

2. XOR fold

XOR all values. Duplicates cancel, lone value remains.

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

Tradeoff:

TripAdvisor-specific tips

TripAdvisor uses bitwise puzzles to gauge if you spot constant-space tricks when scanning review-id streams for orphans.

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

Practice these live with InterviewChamp.AI →