260. Single Number III solved in rust

Link

260. Single Number III

Problem

The problem is asking to find the two numbers that appear only once in an array of numbers. The array contains numbers that appear twice except for two numbers that appear only once.

We are asked to provide a (O(n) time, O(1) space) solution.

Key

Another type of problem, unsolvable without a key. In order to solve this you need to have knowledge of the XOR operation, and the tricks you can do with it.

First step is to XOR all the numbers in the array. XOR has the property a ^ a = 0 or it will cancel out the numbers that will appear twice. The result will be the XOR of the two numbers that appear only once.

So if we XOR all the numbers from the input array:

[1, 2, 1, 3, 2, 5]

1 ^ 2 ^ 1 ^ 3 ^ 2 ^ 5 = 3 ^ 5 = 6

Since the result is 6, we can say that the two numbers that appear only once are different in the 2nd and 3rd bit. We can use this information to separate the numbers in two groups. One group will have the 2nd bit set to 0, and the other group will have the 2nd bit set to 1.

 0  [1] 1 = 3
^
[1]  0  1 = 5
---
 1   1  0

Now we can XOR the numbers in each group to find the numbers that appear only once.

Solution

pub struct Solution;

impl Solution {
    pub fn single_number(nums: Vec<i32>) -> Vec<i32> {
        // stage one we do the XOR of all the numbers
        let xor = nums.iter().fold(0, |mut acc, it| {
            acc ^= it;

            acc
        });


        // we find the first bit that is different
        let mut diff_bit = 1;

        while xor & diff_bit == 0 { // we stop when we find the if the bit is set
            diff_bit <<= 1;
        }

        // we will use the diff_bit to separate the numbers in two groups
        let mut first = 0;
        let mut second = 0;

        for num in nums {
            if num & diff_bit != 0 {
                first ^= num;
            } else {
                second ^= num;
            }
        }

        vec![first, second]
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn it_works() {
        let scenarios = vec![
            (vec![1, 2, 1, 3, 2, 5], vec![3, 5]),
            (vec![-1, 0], vec![-1, 0]),
            (vec![0, 1], vec![1, 0]),
        ];

        scenarios
            .into_iter()
            .enumerate()
            .for_each(|(idx, (input, expected))| {
                let result = Solution::single_number(input);
                assert_eq!(result, expected);
                println!("  ✓ scenario {}", idx + 1)
            });
    }
}