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.
