@SAM: in your first step, where you are xoring the unique elements, you must be using some DS such as hashtable or something.....
so space complexity will be O(n)..... can someone reduces this O(n) space complexity.....because it wont be a good approach if there are many elements in the array.... On Fri, Nov 18, 2011 at 9:26 AM, SAMM <somnath.nit...@gmail.com> wrote: > On 11/18/11, SAMM <somnath.nit...@gmail.com> wrote: > > For example the array has .. > > 1 4 2 6 7 4 8 3.. > > xor the elements in the array will give (1^2^6^7^8^3). > > > > now xor the unique elements using hash table ,It gives (1^4^2^6^7^8^3). > > Now xor these two value which gives 4. > > > > On 11/18/11, Dave <dave_and_da...@juno.com> wrote: > >> @SAMM: It sounds like a circular argument. How do you XOR all of the > >> unique elements without first finding the repeated ones? > >> > >> Dave > >> > >> On Nov 17, 11:24 am, SAMM <somnath.nit...@gmail.com> wrote: > >>> Yes we can do so in O(n) . > >>> > >>> First find the XOR of all unique elements using hash table or some > >>> other > >>> DS. > >>> Secondly XOR all the elements of the array .which will hav the xor of > >>> elements other thn the element repeated twice. > >>> > >>> Now XOR the above two value which will give the answer.. > >>> > >>> On 11/17/11, himanshu kansal <himanshukansal...@gmail.com> wrote: > >>> > >>> > >>> > >>> > >>> > >>> > consider an array having n elements.....out of which one number is > >>> > repeated twice....other number are repeated odd number of times(for > >>> > simplicity, assume other numbers are occurring just once).... > >>> > >>> > can you find the number that is repeated twice in O(n) time??? > >>> > >>> > PS: numbers are not from a particular range..... > >>> > >>> > -- > >>> > 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. > >>> > >>> -- > >>> Somnath Singh > >> > >> -- > >> 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. > >> > >> > > > > > > -- > > Somnath Singh > > > > > -- > Somnath Singh > > -- > 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. > > -- Regards Himanshu Kansal Msc Comp. sc. (University of Delhi) -- 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.
