Does this means that all the integers from 0 to 2^32 are present and only one is missing? That's how I am interpreting this problem.Correct if wrong.
On Mon, Jul 18, 2011 at 10:37 AM, ankit sambyal <ankitsamb...@gmail.com>wrote: > Total no. of nos. =4b=2^32 > Memory = 2^16 bytes > No. of bins = 2^16/4 = 2^14 > Max nos. in each bin = 2^32 / 2^14 = 2^18 > > But there's a problem. There is integer 0 also. > So, maximum nos. in the first bin = 2^18 + 1 > > ALGO: > 1. Set the count of each bin =0 > 2. Scan through the nos. and increment the count > 3. If any bin has count less than the max for that bin, it means that > the missing integer belongs to that bin > 4. Now take a bit vector of 2^18 bits or 2^18 + 1 bits according to > the max count of the bin in which the number is missing. > 5. Scan through the list of integers. If the integer belongs to the > bin from which the number is missing, set the corressponding bit of > the bit vector. > 6. Now find the bit of bit vector which is not set. By knowing this > bit, we can easily tell which integer was missing. > > > > The presence of negative numbers do not affect the solution. Since the > list contains 2^32 numbers and an integer takes 4 bytes, so we have > handled negative integers, since we have taken integers as unsigned. > > -- > 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 > algogeeks+unsubscr...@googlegroups.com. > 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.