Home > Algorithms > You are given an array of n+2 elements. All elements of the array occur once between 1 and n except two numbers which occur twice. Find the two repeating numbers in O(n) (eg) say for n = 5

You are given an array of n+2 elements. All elements of the array occur once between 1 and n except two numbers which occur twice. Find the two repeating numbers in O(n) (eg) say for n = 5

July 7, 2012

Question:

You are given an array of n+2 elements. All elements of the array occur once between 1 and n except two numbers which occur twice. Find the two repeating numbers in O(n)

(eg) say for n = 5

array = 4 2 4 5 2 3 1

The above array has n+2=7 elements with all elements occurring once except 2 and 4 which occurs twice. Find those repeating numbers in O(n) time and constant space.

The output should be 4 2.

Solution: Let summation of all numbers in array be S and product be P

Let the numbers which are being repeated are X and Y.

X + Y = S – n(n+1)/2
XY = P/n!

Using above two equations, we can find out X and Y. For array = 4 2 4 5 2 3 1, we get S = 21 and P as 960.

X + Y = 21 – 15 = 6

XY = 960/5! = 8

X – Y = sqrt((X+Y)^2 – 4*XY) = sqrt(4) = 2

Using below two equations, we easily get X = 4 and Y = 2
X + Y = 6
X – Y = 2

Advertisements
Categories: Algorithms
%d bloggers like this: