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.