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
On Mon, Jul 18, 2011 at 5:57 PM, varun pahwa <varunpahwa2...@gmail.com>wrote: > sorry that would not work. only it could work if each element is present > exactly once. > > > On Mon, Jul 18, 2011 at 5:44 PM, Aakash Johari <aakashj....@gmail.com>wrote: > >> Yes, you will have to write a quad eq. solver. It's easy to write. >> >> >> On Mon, Jul 18, 2011 at 5:13 AM, Aakash Johari <aakashj....@gmail.com>wrote: >> >>> @varun: can you write the code for one? >>> >>> >>> On Mon, Jul 18, 2011 at 5:11 AM, varun pahwa >>> <varunpahwa2...@gmail.com>wrote: >>> >>>> 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. >>>> >>>> >>>> On Mon, Jul 18, 2011 at 5:31 PM, ankit sambyal >>>> <ankitsamb...@gmail.com>wrote: >>>> >>>>> 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 post to this group, send email to algogeeks@googlegroups.com. >>>>> To unsubscribe from this group, send email to >>>>> algogeeks+unsubscr...@googlegroups.com. >>>>> 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 >>>> Official Email :: rit2008...@iiita.ac.in >>>> Another Email :: varunpahwa.ii...@gmail.com >>>> >>>> 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 post to this group, send email to algogeeks@googlegroups.com. >>>> To unsubscribe from this group, send email to >>>> algogeeks+unsubscr...@googlegroups.com. >>>> 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 post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> 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 > Official Email :: rit2008...@iiita.ac.in > Another Email :: varunpahwa.ii...@gmail.com > > 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 post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > 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@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
