Medium · XOR Partition
Understand → Visualise → Practice.
Exactly two values occur once and every other value twice. Return the two singletons in ascending order.
XOR of everything equals a ^ b of the two singles. Any set bit in it separates a from b, and partitioning by that bit puts each single in its own group, where duplicates cancel.
x = XOR of all values = a ^ b.
bit = x & −x isolates the lowest bit where a and b differ.
XOR values with that bit set into one total and the rest into another; return the two totals in ascending order.
O(n) time and O(1) space.
Returning the two values in discovery order fails the ascending-order requirement.
Read the full guide first: Bit Manipulation and Bitmask Patterns.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.