Find the two non-repeating elements (all others appear twice)
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]
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];}