Coding problem · Easy · Basics

The Single Number

Easy Algorithms & data structures

In nums, every value appears exactly twice except one, which appears once. Return that single value.

Example 1

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

Example 2

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

Hints

Hint 1

A set works: add a value the first time, remove it the second time.

Hint 2

Bonus trick: XOR of a number with itself is 0, and XOR with 0 keeps the number.

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(n) · Space O(1)

XOR all the values: pairs cancel out (x ^ x = 0) and the single number remains (0 ^ y = y). O(n) time, O(1) space.

Reference solution

function singleNumber(nums) {
  return nums.reduce((acc, n) => acc ^ n, 0);
}

function singleNumber(nums: number[]): number {
  return nums.reduce((acc, n) => acc ^ n, 0);
}

def single_number(nums: list[int]) -> int:
    result = 0
    for n in nums:
        result ^= n
    return result

<?php

function singleNumber(array $nums): int
{
    $result = 0;
    foreach ($nums as $n) {
        $result ^= $n;
    }
    return $result;
}

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int n : nums) result ^= n;
        return result;
    }
}

Was this page helpful?