Find missing number in 4 billion integers - PrismoSkills

Find missing number in 4 billion integers - PrismoSkills

Find missing number in 4 billion integers Problem: Using 1GB of memory only, find the missing numbers in 4 billion integers stored in a file. Solution: One integer takes 4 bytes, so 4 billion integers would take: 4 bytes * (4 * 109) = 16 GB Since we have only 1 GB of memory, we cannot get all the integers into memory at once. Even if we could get all numbers into memory, we would need some data-structure like an array where each integer from the 4 billion lot would be kept and then we will scan the array to find holes. The array to store the 4 billion integers need not be of type int [] It can be of type boolean [] also since all we need is a true/false to know whether an int is present or not. Memory required to store 4 billion booleans = 1 bit * (4 * 109) = 4Gb = 0.5 GB (small b means bit and capital B means bytes). So this seems doable with 1 GB of memory. We have a boolean array as boolean numberPresent[4*1000*1000*1000],

Read full article from Find missing number in 4 billion integers - PrismoSkills