Hi Googmeister, You wrote "but the idea easily extends to arbitrary n" Could you explain how ?
Thanks, AlgoStudent On Jun 21 2006, 9:43 pm, "Googmeister" <[EMAIL PROTECTED]> wrote: > anil kumar wrote: > > An array A[1..n] contains all the integers from 0 to n except one. It > > would be easy to determine themissingintegerin O(n) time by using an > > auxilary array B[0..n] to record which numbers appear in A. In this > > problem however we cannot access an entireintegerin A with a single > > operation. The elements of A are represented in binary, the only > > operation we can use to access them is " Fetch the jth bit of A[i] " , > > which takes constant time.Findthemissingintegerin O(n) time using > > only that operation. > > Are you permitted to swap array entries in constant time? > If so, the following is a solution. I'll assume n is a power of 2 > for simplicity (but the idea easily extends to arbitrary n). > > Scan through the leading bits of the n integers. Themissingintegerstarts with 0 if 0 appears an odd number of times, > and 1 otherwise. Move all the integers starting with the same > leading bit as themissingintegerto one side of the array > (e.g., ala partitioning in quicksort). Now recur on those > remaining integers and the next most significant bit. There > are lg n phases since the number of bits perintegeris lg n, > but the overall running time is still linear: n + n/2 + n/4 + > ...<[email protected]> --~--~---------~--~----~------------~-------~--~----~ 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.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
