DSA problem
Single Number III
Given an integer array nums in which exactly two elements appear only once and all the other elements appear exactly twice, find the two elements that appear only once. You may return the answer in any order.
You must write an algorithm that runs in linear time and uses only constant extra space.
XOR-ing the entire array cancels every paired element and leaves xorAll = a ^ b, where a and b are the two unique numbers. Since a and b are distinct, xorAll has at least one set bit; that bit position is where a and b differ.
Pick any one such set bit (conveniently the lowest, via xorAll & -xorAll). This bit partitions the array into two groups: numbers with the bit set and numbers without it. Each unique number falls into a different group, and every duplicate pair lands together in the same group. XOR-ing each group separately recovers a and b.
Examples
nums = [1,2,1,3,2,5][3,5]nums = [-1,0][-1,0]nums = [0,1][1,0]Constraints
- 2 <= nums.length <= 3 * 10^4
- -2^31 <= nums[i] <= 2^31 - 1
- Each integer in nums will appear twice, only two integers will appear once.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.