array has all distinct elements ans lie b/w 1 to n , now bcozz they are all
distinct except 1 element means it should have all element with range 1 to
n...except 1 element , which can be any element b/w 1 to n.
temp=arr[0]
*for i=1 to n
temp=temp^arr[i]; *
//now temp will contain all distinct elements except one which is
repeated(they cancel out)
*for i=1 to n
temp=temp ^ i; *
// now this will cancel out distinct elements excluding one which is
repeated.
temp will contain that repeated element
On Sun, Nov 18, 2012 at 7:31 PM, shady <sinv...@gmail.com> wrote:
> Given an array of size n, which has all distinct elements between 1 to n
> with one element repeating, which also implies that one element is missing.
> How to find the repeating element without using extra space and linear
> time complexity ?
>
> Any way to do it with exor ? :P
>
> --
>
>
>
--
