Cracking The Coding Interview

Find the two repeating elements in a given array.

You are given an array of n+2 elements. All elements of the array are in range 1 to n. And all elements occur once except two numbers which occur twice. Find the two repeating numbers.

For example, array = {4, 2, 4, 5, 2, 3, 1} and n = 5

The above array has n + 2 = 7 elements with all elements occurring once except 2 and 4 which occur twice. So the output should be 4 2.

Answer: Let repeated numbers are A and B. Find sum and product of arrey, lets say S and P.

Then eqn---1 A+B = s - n(n+1)/2

AB = p/n!

eqn------2

A - B = sqr_root ((A-B)^2 - 4AB)

Now you have 2 variables and 2 equations. Solve the equations and get the values.

This post was written by: Franklin Manuel

Franklin Manuel is a professional blogger, web designer and front end web developer. Follow him on Twitter