Find the 2 removed numbers from an array of all numbers 1-n

Question

Find the 2 removed numbers from an array of all numbers 1...n. The array order is randomized and no hashmaps are allowed.

I got the following hints:

• Mark the 2 numbers with x and y... (But I'm not sure what to do with that)
• Maybe use the sum somehow?

At the end I wasn't told the correct solution and I still have no clue.

Of course, a O(nlogn) algorithm is easy, but the challenge asks for a O(n) time complexity.

With no hashmaps/hashsets allowed, I didn't see how to approach this. I mean, how is this possible without them?

How could we find the two missing numbers in O(n) time?

Answer 1

You could calculate what the sum and the sum of squares is of the given numbers, and compare that with what those sums would have been if the array would have also included the two missing values 𝑥 and 𝑦.

This gives you two equations:

• 𝑥 + 𝑦 = 𝑞
• 𝑥² + 𝑦² = 𝑝

Where 𝑞 is the difference between the "expected" sum and the actual sum, and 𝑝 is the difference of the expected sum of squares and the actual sum of squares.

By substituting 𝑦, the above can be rewritten as:

• 2𝑥² − 2𝑞𝑥 + 𝑞²−𝑝 = 0

The two solutions to that equation are the values for 𝑥 and 𝑦:

• 𝑥 = [𝑞 ± √(2𝑝 − 𝑞²)] / 2

Here is an implementation in JavaScript, where two random numbers are removed from a sequence from 1 to 20, and the algorithm retrieves the missing values (as the algorithm doesn't use the order of the input, I didn't bother to shuffle the input):

function createInput(n) {
    const arr = [...Array(n+1).keys()]; // {0,1,...,n}
    arr.shift(); // Remove 0 => {1,...,n}
    for (let removals = 1; removals <= 2; removals++) {
        const i = Math.floor(Math.random() * arr.length);
        arr.splice(i, 1); // Remove random element
    }
    return arr;
}

function findXY(arr) {
    const n = arr.length + 2;
    // Expected sum and sumOfSquares
    let sum = n * (n + 1) / 2;
    let sumSquares = sum * (2 * n + 1) / 3;
    // Subtract the actual sums
    for (let i = 0; i < arr.length; i++) {
        sum -= arr[i];
        sumSquares -= arr[i] * arr[i];
    }
    // Solution to quadratic equation
    const x = (sum - Math.sqrt(2 * sumSquares - sum * sum)) / 2;
    return [x, sum - x];
}

for (let run = 1; run <= 4; run++) {
    const arr = createInput(20);
    console.log("input  : ", ...arr);
    console.log("missing: ", ...findXY(arr));
}