codejump
MediumPythonJavaScriptTypeScript

Bits — Single Number III (Two Singles)

AlgorithmsBit ManipulationArrays

solve(nums) — exactly two values of nums (non-negative, < 2^31) appear once;
every other value appears twice. Return the two singles as [smaller, larger], in O(n)
time and O(1) extra space.

XOR-ing everything gives a ^ b for the two singles — non-zero because a !== b. Any
set bit of that result is a position where a and b differ. Pick the lowest one with
x & -x, split nums into two groups by whether they have that bit, and XOR each group:
pairs stay together and cancel, and each group isolates one single.

Examples

solve([1,2,1,3,2,5])   → [3,5]
solve([0,1])           → [0,1]
solve([4,1,2,1,2,6])   → [4,6]

Sample tests

Test #1Classic example
Input: [[1,2,1,3,2,5]]
Output: [3,5]
Test #2Only the two singles
Input: [[0,1]]
Output: [0,1]
Test #3Singles at both ends
Input: [[4,1,2,1,2,6]]
Output: [4,6]
← All challenges