On 11/17/06, Arun <[EMAIL PROTECTED]> wrote: > > 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)) ) still too slow. There is an O(n) solution :) > > 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 -~----------~----~----~----~------~----~------~--~---
