No. This works for all cases. Xor is commutative.
On 2010-2-5 13:37, srinivas chintagunta wrote:
I think this works if elements are sorted . Is it correct?
On Mon, Feb 1, 2010 at 5:07 PM, sachin <[email protected]
<mailto:[email protected]>> 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 [email protected]
<mailto:[email protected]>.
To unsubscribe from this group, send email to
[email protected]
<mailto:algogeeks%[email protected]>.
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 [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.
--
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.
