If we do this we cannot achieve O(n) running time. Here we can access only one bit at a time. Abhijit
On 5/14/07, Kumaraguru Paramasivam <[EMAIL PROTECTED]> wrote: > > Find the sum of all the numbers in the array.[s1] > > Since the array contains integers from 0 or 1 to 'n'. > Find the sum of this first n natural numbers n(n+1)/2. [s2] > > Missing number = [s2] - [s1] > > > On 5/12/07, You I <[EMAIL PROTECTED]> wrote: > > > 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 -~----------~----~----~----~------~----~------~--~---
