@Ankit: when we say 32 bits for an int i.e 2^32 values, 0 is considered in those 2^32 values.. right? So, y that extra +1?
On Jul 18, 10:07 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.
