I don't think it can be done in better than O(n) space and time. On Tue, Nov 22, 2011 at 9:28 PM, himanshu kansal < himanshukansal...@gmail.com> wrote:
> @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. > -- Nitin Garg "Personality can open doors, but only Character can keep them open" -- 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.
