problem

In the town of Digitville, there was a list of numbers called nums containing integers from 0 to n - 1. Each number was supposed to appear exactly once in the list, however, two mischievous numbers sneaked in an additional time, making the list longer than usual.

As the town detective, your task is to find these two sneaky numbers. Return an array of size two containing the two numbers (in any order), so peace can return to Digitville.

 

Example 1:

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

Output: [0,1]

Explanation:

The numbers 0 and 1 each appear twice in the array.

Example 2:

Input: nums = [0,3,2,1,3,2]

Output: [2,3]

Explanation:

The numbers 2 and 3 each appear twice in the array.

Example 3:

Input: nums = [7,1,5,4,3,4,6,0,9,5,8,2]

Output: [4,5]

Explanation:

The numbers 4 and 5 each appear twice in the array.

 

Constraints:

  • 2 <= n <= 100
  • nums.length == n + 2
  • 0 <= nums[i] < n
  • The input is generated such that nums contains exactly two repeated elements.

submission

// we can XOR every number from both nums and 0..n, then
// this question is reduced to single number III
// Another intuition is to place each number into their
// index, we'll find two duplicates that have no position
// to place.
impl Solution {
    pub fn get_sneaky_numbers(mut nums: Vec<i32>) -> Vec<i32> {
        let cycle = |nums: &mut [i32], idx: usize| {
            // keep cycling until we find the duplicate
            while nums[idx] != nums[nums[idx] as usize] {
                nums.swap(idx, nums[idx] as usize);
            }
        };
        let n = nums.len() - 2;
        // place the duplicates on pos n and n+1
        cycle(&mut nums, n);
        cycle(&mut nums, n + 1);
        vec![nums[n], nums[n + 1]]
    }
}