1) Scan through the array counting number of 0s and 1s in MSB, as well as separating the 0s into an array arr0 and 1s into an array arr1 (if you do not want to use extra space you can use splitting around pivot pass of quicksort). 2) You would know how many 0s and 1s should be present in MSB for the number 1 ... n (this would be n/2 and n/2 if n is a power of 2). 3) Either the 0s or 1s would be less, so the missing number has that digit as MSB. 4) Take that bucket i.e. arr0 or arr1 and repeat steps 1 to 3.
The complexity of this is n + n/2 + n/4 ... = 2n = O(n). -Dhyanesh > 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 [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
