the original problem if the array is unsorted, u can do it, by counting the number of 1's (and hence 0's), in each bit position. (i.e vertically scan thru all the numbers once for each bit position). given any n, u know how many 1's shud be present in msb,2nd msb and so-on. based on this u can find the missing number but this is O(n . (number of bit positions - which is atmost lg(n)) )
to make the problem easier I have made the assumption that array is sorted :-) since the array is sorted , u know that there will be 2 ^(n-1) 0's followed by 2 ^(n-1) 1's in the MSB(most significatn bit) and 2 ^(n-2) 0's and followed by 2^(n-1) 1's repeated twice. So in general, u have for ith significant bit (i=1 means msb), 2^(n-i) 0s then 2^(n-i) 1s repeated i times. Now just do a binary search. Starting with the msb, extract(i,n/2) . if its 1(supposed to be 0), the missing number is in first half(and msb of missing number is 0). do the same for second msb and so on... comlpexity = O(lg n) , for n=2^k. On 11/17/06, Norbert < [EMAIL PROTECTED]> wrote: > > > extract(i, n) - i'th bit from position n in an array A - i'th bit of A[n] > > On 11/17/06, Idris <[EMAIL PROTECTED]> wrote: > > > > > > Is this extracting i'th bit from a[X] or just extracting Integer from i > > th index of an array??? > > > > if its the later, then get the number and sum up by using OR > > operation.... not sure:-) > > > > then subtract it from n(n+1)/2="missing Number" > > > > > > > > > > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
