Single Number
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
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);