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

*Post by varun pahwa*sorry that would not work. only it could work if each element is present

exactly once.

*Post by Aakash Johari*Yes, you will have to write a quad eq. solver. It's easy to write.

*Post by Aakash Johari*@varun: can you write the code for one?

*Post by varun pahwa*The above solution will work if each other number is exactly once

present. but if that 's not true.

then 4 equations can be formed.

Assuming a,b repeated number where a may or may be equal to b.

then equations will be

x + y = a + b;

x^2 + y^2 = a^2 + b^2.

x.y = a.b

x^3 + y^3 = a^3 + b^3.

now 4 equations 4 variables can be solved.

*Post by ankit sambyal*1. Initialize a bit vector of size n.

2. For every no. set the corresponding bit vector.

3. Now scan through the bit vectors and get the missing numbers

corressponding to the unset bits in the bit vector.

Time complexity : O(n)

--

You received this message because you are subscribed to the Google

Groups "Algorithm Geeks" group.

To unsubscribe from this group, send email to

For more options, visit this group at

http://groups.google.com/group/algogeeks?hl=en.

--

Varun Pahwa

B.Tech (IT)

7th Sem.

Indian Institute of Information Technology Allahabad.

Ph : 09793899112

People who fail to plan are those who plan to fail.

--

You received this message because you are subscribed to the Google

Groups "Algorithm Geeks" group.

To unsubscribe from this group, send email to

For more options, visit this group at

http://groups.google.com/group/algogeeks?hl=en.

--

-Aakash Johari

(IIIT Allahabad)

--

-Aakash Johari

(IIIT Allahabad)

--

You received this message because you are subscribed to the Google Groups

"Algorithm Geeks" group.

To unsubscribe from this group, send email to

For more options, visit this group at

http://groups.google.com/group/algogeeks?hl=en.

--

Varun Pahwa

B.Tech (IT)

7th Sem.

Indian Institute of Information Technology Allahabad.

Ph : 09793899112

People who fail to plan are those who plan to fail.

--

You received this message because you are subscribed to the Google Groups

"Algorithm Geeks" group.

To unsubscribe from this group, send email to

For more options, visit this group at

http://groups.google.com/group/algogeeks?hl=en.

--

You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.

To post to this group, send email to algogeeks-/JYPxA39Uh5TLH3MbocFF+G/***@public.gmane.org

To unsubscribe from this group, send email to algogeeks+***@googlegroups.com.

For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.