problem

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 can return the answer in any order.

You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.

 

Example 1:

Input: nums = [1,2,1,3,2,5]
Output: [3,5]
Explanation:  [5, 3] is also a valid answer.

Example 2:

Input: nums = [-1,0]
Output: [-1,0]

Example 3:

Input: nums = [0,1]
Output: [1,0]

 

Constraints:

  • 2 <= nums.length <= 3 * 104
  • -231 <= nums[i] <= 231 - 1
  • Each integer in nums will appear twice, only two integers will appear once.

submission

// we solve this in two passes
// the first pass is the same as single number
// let say what we search is a and b, and a != b
// we XOR all the numbers and get xor = a ^ b
// a != b -> xor != 0
// in the second pass, we separate numbers into
// two groups, one with a and another with b
// how? by check a single set bit in xor
// if a bit is set in xor, a and b must have different
// value in this bit, and rest pairs must fallen into
// either group and won't affect us.
// we then XOR each group and get what we want
impl Solution {
    pub fn single_number(nums: Vec<i32>) -> Vec<i32> {
        let mask = nums.iter()
            .fold(0, std::ops::BitXor::bitxor);
        let distinguishing_bit = 1 << mask.trailing_zeros();
        let first = nums.iter()
            .filter(|&&v| v & distinguishing_bit == 0)
            .fold(0, std::ops::BitXor::bitxor);
        vec![first, first ^ mask]
    }
}