Given an array of size n. It contains numbers in the range 1 to n.Each number is present at least once except for 2 numbers. Find the missing numbers ?
Method I :
Assume array a ={1,2,3,3,5};
element n=3 is repeated and m=4 is missed.
Sum of the elements actual = 1+2+3+3+5
Sum of the elements expected = 1+2+3+4+5
Diff expected-actual = 4-3=m-n ==> m-n=1 ----------------- Eq1
expected product = 1*2*3*3*5;
actual product = 1*2*3*4*5;
expected/actual = 3/4=n/m ===> 3m=4n; --------------------Eq2
We have two equations.We can find m and n now.
Method II : We can solve it using bitwise opertions.
1.Calculate XOR of all the array elements.
2.XOR the result with all numbers from 1 to n =>x1
3.After 2nd step, all elements would nullify each other except 2 missing elements(let x and y) and x1 will contain XOR of x and y
4.All the bits that are set in x1 will be set in either x or y. Get the rightmost set bit from x1.
5.divide the elements of the array in two sets – one set of elements with same bit set and other set with same bit not set. By doing so, you will get x in one set and y in another set.
6.XOR all the elements of 1st set with the numbers between 1 to n which have same bit set and XOR the 2nd set with the numbers between 1 to n which have same bit not set. Now result of both set will have the desired result
Method III : We can solve it using hashmap also.
Method I :
Assume array a ={1,2,3,3,5};
element n=3 is repeated and m=4 is missed.
Sum of the elements actual = 1+2+3+3+5
Sum of the elements expected = 1+2+3+4+5
Diff expected-actual = 4-3=m-n ==> m-n=1 ----------------- Eq1
expected product = 1*2*3*3*5;
actual product = 1*2*3*4*5;
expected/actual = 3/4=n/m ===> 3m=4n; --------------------Eq2
We have two equations.We can find m and n now.
Method II : We can solve it using bitwise opertions.
1.Calculate XOR of all the array elements.
2.XOR the result with all numbers from 1 to n =>x1
3.After 2nd step, all elements would nullify each other except 2 missing elements(let x and y) and x1 will contain XOR of x and y
4.All the bits that are set in x1 will be set in either x or y. Get the rightmost set bit from x1.
5.divide the elements of the array in two sets – one set of elements with same bit set and other set with same bit not set. By doing so, you will get x in one set and y in another set.
6.XOR all the elements of 1st set with the numbers between 1 to n which have same bit set and XOR the 2nd set with the numbers between 1 to n which have same bit not set. Now result of both set will have the desired result
Method III : We can solve it using hashmap also.
No comments:
Post a Comment