Re: [algogeeks] Re: array searching
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 twiceother 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.
Re: [algogeeks] Re: array searching
@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 twiceother 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.
[algogeeks] Re: array searching
@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 twiceother 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.
Re: [algogeeks] Re: array searching
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 twiceother 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.
