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