I think this works if elements are sorted . Is it correct?
On Mon, Feb 1, 2010 at 5:07 PM, sachin <sachin_mi...@yahoo.co.in> wrote:
> A way to solve this problem would be using xor(exclusive OR)
> xor all the elements from 1 to n.Call it A
> xor all the elements of the array into a variable B
> Now missing element = A xor B
> It works this way
> xor-ing an element with itself gives 0(p xor p=0)
> xor-ing an element with 0 gives the element itself(p xor 0=p)
> xor-ing an element with 1 gives the complement of element(p xor
> 1=complement(p))
>
> Now suppose you are given 4 elements and you have to find the missing
> 5th element
> A=1 xor 2 xor 3 xor 4 xor 5;
> B=ar[1] xor ar[2] xor ar[3] xor ar[4];
>
> let array be {2,5,3,1}
> thus, B=1 xor 2 xor 3 xor 5;
>
> Now A xor B = (1 xor 1) xor (2 xor 2) xor (3 xor 3) xor (5 xor 5) xor
> 4 = 0 xor 0 xor 0 xor 0 xor 4 = 4(the missing element).
>
> Regards
> Sachin
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
Srinivas Chintagunta,
Hyderabad.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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.
