neat solution :) On 11/17/06, Dhyanesh (ધયાનેશ) <[EMAIL PROTECTED]> wrote: > > 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 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 -~----------~----~----~----~------~----~------~--~---
