question

Please attempt part 1 of this question if you haven't tried it yet.

An array is filled with the numbers from 1 through 1,000,000 (inclusive), with the exception of two missing numbers. The array has been filled randomly with each number used only once. Determine the two missing numbers in one pass through the data.

An array is filled with the numbers from 1 through 1,000,000 (inclusive), with the exception of two missing numbers. The array has been filled randomly with each number used only once. Determine the two missing numbers in one pass through the data.

As in part 1 of this question we'll iterate through the list and calculate the sum of the numbers given to us (sum). Though this time, we'll also calculate the sum of the squares of the numbers (sumSquares). This is because since we have two unknowns we'll need two equations.

Next calculate the sum from 1 through 1,000,000 using the summation formula ( Σ = [n * (n+1)] / 2 where n = 1,000,000). Similarly calculate the sum of squares in the total range giving us the below equations.

totalSum = 1 + 2 + ... + 1,000,000 = [n * (n+1)] / 2 = 500000500000

totalSumSquares = 1

Using the above total sums, we can derive the below equations with our missing numbers, a & b:

a + b = totalSum - sum

a

Solving the two equations will give us our missing numbers. The same logic can be extended to n missing numbers. Simply calculate the sums to nth degree to give the appropriate number of equations necessary to solve.

Thoughts or alternate solution? Let us know in the comments below!

Next calculate the sum from 1 through 1,000,000 using the summation formula ( Σ = [n * (n+1)] / 2 where n = 1,000,000). Similarly calculate the sum of squares in the total range giving us the below equations.

totalSum = 1 + 2 + ... + 1,000,000 = [n * (n+1)] / 2 = 500000500000

totalSumSquares = 1

^{2}+ 2^{2}+ ... + 1,000,000^{2}= [n * (n + 1) * (2n + 1)] / 6 = 333333833333500000Using the above total sums, we can derive the below equations with our missing numbers, a & b:

a + b = totalSum - sum

a

^{2}+ b^{2}= totalSumSquares - sumSquaresSolving the two equations will give us our missing numbers. The same logic can be extended to n missing numbers. Simply calculate the sums to nth degree to give the appropriate number of equations necessary to solve.

Thoughts or alternate solution? Let us know in the comments below!