Find the two non-repeating elements (all others appear twice)

Medium

Problem

Every element appears exactly twice, except two elements that appear once. Return those two, in O(n) time and O(1) space.

Example 1

Input:  [1, 2, 1, 3, 2, 5]
Output: [3, 5]

Also asked as: Find the two non-repeating elements in an array of repeating elements

Test cases

Case 1

Input:    [1,2,1,3,2,5]
Expected (any order): [3,5]

Case 2

Input:    [2,1,3,2]
Expected (any order): [1,3]

Case 3

Input:    [7,9]
Expected (any order): [7,9]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. XOR everything, split by a differing bit

Time O(n)Space O(1)

XOR of the whole array = x ^ y. Any set bit in it differs between x and y — partition the array by that bit and XOR each group separately.

function twoNonRepeating(a) {
const xorAll = a.reduce((acc, v) => acc ^ v, 0);
const bit = xorAll & -xorAll; // lowest set bit
let x = 0, y = 0;
for (const v of a) (v & bit) ? (x ^= v) : (y ^= v);
return [x, y];
}