Well I like Samm's approach.Another possible approach would be adding all the numbers.The result should fit in long long(2^32 numbers*max_int=2^64).Precompute the sum of 2^64 numbers by big int arithematic.Subtract to get the missing numbers.Again o(1) space and o(n) time though slower than SAMM's approach.
PS:Though I still doubt the problem requires the same.Dumanshu can u quote the source of the problem please? On Mon, Jul 18, 2011 at 12:06 PM, ankit sambyal <[email protected]>wrote: > @lalit : I wanted to use bit vector to find the missing no. since the > list contains all the numbers from 0 to 2^32 except one missing no. > But it would require a bit vector of 2^32 bits which won't fit in > memory. So, I found the narrowed the range in which the missing no. > lies and then applied the bit vector concept. I hope its clear now ... > > -- > 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?hl=en. > > -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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?hl=en.
