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 < [email protected]> 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 <[email protected]> wrote: > >> On 11/18/11, SAMM <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 [email protected]. >> >>> > To unsubscribe from this group, send email to >> >>> > [email protected]. >> >>> > 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 [email protected]. >> >> To unsubscribe from this group, send email to >> >> [email protected]. >> >> 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
