Single Number

Examples

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

2 appears twice; 1 appears only once.

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

1 and 2 each appear twice; 4 appears only once.

Input: nums = [1]
Output: 1

Constraints

• 1 <= nums.length <= 3 * 10^4

• -3 * 10^4 <= nums[i] <= 3 * 10^4

• Every element appears twice, except for exactly one which appears once.

Approach

The direct way to solve this is to count how many times each number occurs, using a hash map, and return the one whose count is 1. That works, but it needs extra memory proportional to the number of distinct values in the list.

XOR (bitwise exclusive-or, the ^ operator) offers a way to do this with no extra memory at all. Think about what XOR does bit by bit: a bit XORed with an identical bit gives 0, and a bit XORed with 0 stays unchanged. That means XORing any number with itself always gives 0, and XORing a number with 0 always gives that number back. If you XOR every number in the list together in one running total, every pair of identical values cancels itself out to 0, no matter what order they appear in - leaving only the single number that had no partner to cancel with.

Solutions

Brute Force - Count With a Hash Map

Count how many times each number appears using a hash map, then return the one whose count is exactly 1.

function singleNumber(nums) {
  const counts = new Map();

  for (const num of nums) {
    counts.set(num, (counts.get(num) || 0) + 1);
  }

  for (const [num, count] of counts.entries()) {
    if (count === 1) return num;
  }
}

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

Optimal - XOR Everything Together

XOR every number in the list into a single running result, starting from 0. Every pair of identical values cancels itself out to 0 along the way (in any order), so whatever value is left over at the end is the one number that appeared just once.

function singleNumber(nums) {
  let result = 0;

  for (const num of nums) {
    result ^= num;
  }

  return result;
}

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