We are given an array of size n2 containing all the numbers

We are given an array of size n-2 containing all the numbers 1,2,....n once excpet two of these numbers that are missing. Example : n=8 A=<3,1,7,8,4,5> The missing numbers are 2 and 6. Give an algorthm that finds the two missing numbers.

Solution

Take all the numbers 1,2,...,n.

Take min{1,2,...,n}. Call it a₁ and arrange it in a new array at the 1st entry.

Repeat the process for the rest upto n-3 times and find a new array in increasing order of 1,2,...,n(except a₁)

(the last step is trivial).

Compare with {1,2,3,,...,n} and identify the missing terms.

For example, in the above case,

1 is the minimum. So the new array starts with 1.

Now min{3,7,8,4,5}=3. So the array is 1,3.

Repeating 4times more the new array becomes {1,3,4,5,7,8}.

Comparing the new array with {1,2,3,4,5,6,7,8}, the missing terms are 2 and 6.