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 longe

getSneakyNumbers.js

/**
 * Finds the two "sneaky" numbers added to an array that originally contained all numbers from 0 to n-1.
 * The final array has length n + 2, and includes two unknown extra numbers.
 *
 * @param {number[]} nums - Array containing numbers from 0 to n-1 plus two extra unknowns.
 * @return {number[]} - The two extra numbers that were added.
 */
var getSneakyNumbers = function (nums) {
    const n = nums.length - 2; // Original range was 0 to n-1, so n = nums.length - 2
    let xorAll = 0;

    // Step 1: XOR all elements in nums
    for (let num of nums) {
        xorAll ^= num;
    }

    // Step 2: XOR all numbers from 0 to n-1
    for (let i = 0; i < n; i++) {
        xorAll ^= i;
    }

    // xorAll now equals the XOR of the two sneaky numbers (let's call them x and y): xorAll = x ^ y

    // Step 3: Find a distinguishing bit (rightmost set bit) to separate x and y
    const diffBit = xorAll & -xorAll;

    let num1 = 0, num2 = 0;

    // Step 4: Partition nums into two groups based on diffBit and XOR within each group
    for (let num of nums) {
        if (num & diffBit) {
            num1 ^= num;
        } else {
            num2 ^= num;
        }
    }

    // Step 5: Do the same partitioning and XOR for numbers 0 to n-1
    for (let i = 0; i < n; i++) {
        if (i & diffBit) {
            num1 ^= i;
        } else {
            num2 ^= i;
        }
    }

    // After XORing both groups, num1 and num2 are the sneaky numbers
    return [num1, num2];
};