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
@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
@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.
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