Single Number

Easy

Problem

Every element appears twice except one. Return that one, in O(n) time and O(1) space.

Example 1

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

Test cases

Case 1

Input:    [2,2,1]
Expected: 1

Case 2

Input:    [4,1,2,1,2]
Expected: 4

Case 3

Input:    [7]
Expected: 7

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. XOR everything

Time O(n)Space O(1)

x ^ x = 0 and x ^ 0 = x, so every pair cancels and the single value remains.

const singleNumber = (nums) => nums.reduce((x, n) => x ^ n, 0);