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 + > > ...<algogeeks@googlegroups.com> > > > --~--~---------~--~----~------------~-------~--~----~ 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.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
