Generate an integer that is not among four billion given ones

Question

I have been given this interview question      Given an input file with four billion integers  provide an algorithm to generate an integer which is not contained in the file  Assume you have 1 nbsp GB memory  Follow up with what you would do if you have only 10 nbsp MB of memory    My analysis   The size of the file is 4  109  4 bytes   16 nbsp GB   We can do external sorting  thus letting us know the range of the integers   My question is what is the best way to detect the missing integer in the sorted big integer sets   My understanding  after reading all the answers    Assuming we are talking about 32-bit integers  there are 232   4 109 distinct integers   Case 1  we have 1 nbsp GB   1   109   8 bits   8 billion bits memory   Solution   If we use one bit representing one distinct integer  it is enough  we don t need sort   Implementation   int radix   8  byte   bitfield   new byte 0xffffffff radix   void F   throws FileNotFoundException      Scanner in   new Scanner new FileReader  a txt         while in hasNextInt             int n   in nextInt            bitfield n radix      1  lt  lt   n radix               for int i   0  i lt  bitfield lenght  i             for int j  0  j lt radix  j                 if   bitfield i   amp   1 lt  lt j      0  System out print i radix j                       Case 2  10 nbsp MB memory   10   106   8 bits   80 million bits     Solution       For all possible 16-bit prefixes  there are 216 number of   integers   65536  we need 216   4   8   2 million bits  We need build 65536 buckets  For each bucket  we need 4 bytes holding all possibilities because the worst case is all the 4 billion integers belong to the same bucket          Build the counter of each bucket through the first pass through the file    Scan the buckets  find the first one who has less than 65536 hit    Build new buckets whose high 16-bit prefixes are we found in step2   through second pass of the file   Scan the buckets built in step3  find the first bucket which doesnt   have a hit          The code is very similar to above one    Conclusion      We decrease memory through increasing file pass      A clarification for those arriving late  The question  as asked  does not say that there is exactly one integer that is not contained in the file mdash at least that s not how most people interpret it  Many comments in the comment thread are about that variation of the task  though  Unfortunately the comment that introduced it to the comment thread was later deleted by its author  so now it looks like the orphaned replies to it just misunderstood everything  It s very confusing  sorry

User · Answer

You can use bit flags to mark whether an integer is present or not.

After traversing the entire file, scan each bit to determine if the number exists or not.

Assuming each integer is 32 bit, they will conveniently fit in 1 GB of RAM if bit flagging is done.

User · Answer

This can be solved in very little space using a variant of binary search    Start off with the allowed range of numbers  0 to 4294967295  Calculate the midpoint  Loop through the file  counting how many numbers were equal  less than or higher than the midpoint value  If no numbers were equal  you re done  The midpoint number is the answer  Otherwise  choose the range that had the fewest numbers and repeat from step 2 with this new range    This will require up to 32 linear scans through the file  but it will only use a few bytes of memory for storing the range and the counts   This is essentially the same as Henning s solution  except it uses two bins instead of 16k

User · Answer

If there is no size limit  the quickest way is to take the length of the file  and generate the length of the file 1 number of random digits  or just  11111     s   Advantage  you don t even need to read the file  and you can minimize memory use nearly to zero  Disadvantage  You will print billions of digits   However  if the only factor was minimizing memory usage  and nothing else is important  this would be the optimal solution  It might even get you a  worst abuse of the rules  award

User · Answer

Surely  and speaking with limited experience  just started learning java at Uni  you can run trhough one set  barrel  of int  and if number not found dispose of barrel  This would both free up space and run a check through each unit of data  If what you are looking for is found add it to a count variable  Would take a long time but  if you made multiple variables for each section and run the check count through each variable and ensure they are exiting disposing at the same time  the variable storage should not increase  And will speed up the check process  Just a thought

User · Answer

Strip the white space and non numeric characters from the file and append 1  Your file now contains a single number not listed in the original file    From Reddit by Carbonetc

User · Answer

Assuming that  integer  means 32 bits  10 MB of space is more than enough for you to count how many numbers there are in the input file with any given 16-bit prefix  for all possible 16-bit prefixes in one pass through the input file  At least one of the buckets will have be hit less than 216 times  Do a second pass to find of which of the possible numbers in that bucket are used already   If it means more than 32 bits  but still of bounded size  Do as above  ignoring all input numbers that happen to fall outside the  signed or unsigned  your choice  32-bit range   If  integer  means mathematical integer  Read through the input once and keep track of the largest number length of the longest number you ve ever seen  When you re done  output the maximum plus one a random number that has one more digit   One of the numbers in the file may be a bignum that takes more than 10 MB to represent exactly  but if the input is a file  then you can at least represent the length of anything that fits in it

User · Answer

If they are 32-bit integers  likely from the choice of  4 billion numbers close to 232   your list of 4 billion numbers will take up at most 93  of the possible integers  4   109    232      So if you create a bit-array of 232 bits with each bit initialized to zero  which will take up 229 bytes   500 MB of RAM  remember a byte   23 bits   8 bits   read through your integer list and for each int set the corresponding bit-array element from 0 to 1  and then read through your bit-array and return the first bit that s still 0   In the case where you have less RAM   10 MB   this solution needs to be slightly modified  10 MB   83886080 bits is still enough to do a bit-array for all numbers between 0 and 83886079   So you could read through your list of ints  and only record  s that are between 0 and 83886079 in your bit array   If the numbers are randomly distributed  with overwhelming probability  it differs by 100  by about 10-2592069  you will find a missing int    In fact  if you only choose numbers 1 to 2048  with only 256 bytes of RAM  you d still find a missing number an overwhelming percentage  99 99999999999999999999999999999999999999999999999999999999999995   of the time   But let s say instead of having about 4 billion numbers  you had something like 232 - 1 numbers and less than 10 MB of RAM  so any small range of ints only has a small possibility of not containing the number     If you were guaranteed that each int in the list was unique  you could sum the numbers and subtract the sum with one   missing to the full sum      232  232 - 1    9223372034707292160 to find the missing int   However  if an int occurred twice this method will fail   However  you can always divide and conquer    A naive method  would be to read through the array and count the number of numbers that are in the first half  0 to 231-1  and second half  231  232    Then pick the range with fewer numbers and repeat dividing that range in half    Say if there were two less number in  231  232  then your next search would count the numbers in the range  231  3 230-1    3 230  232    Keep repeating until  you find a range with zero numbers and you have your answer   Should take O lg N    32 reads through the array   That method was inefficient   We are only using two integers in each step  or about 8 bytes of RAM with a 4 byte  32-bit  integer    A better method would be to divide into sqrt 232    216   65536 bins  each with 65536 numbers in a bin   Each bin requires 4 bytes to store its count  so you need 218 bytes   256 kB   So bin 0 is  0 to 65535 216-1   bin 1 is  216 65536 to 2 216-1 131071   bin 2 is  2 216 131072 to 3 216-1 196607    In python you d have something like     import numpy as np nums in bin   np zeros 65536  dtype np uint32  for N in four billion int array      nums in bin N    65536     1 for bin num  bin count in enumerate nums in bin       if bin count  lt  65536          break   we have found an incomplete bin with missing ints  bin num    Read through the  4 billion integer list  and count how many ints fall in each of the 216 bins and find an incomplete bin that doesn t have all 65536 numbers   Then you read through the 4 billion integer list again  but this time only notice when integers are in that range  flipping a bit when you find them   del nums in bin   allow gc to free old 256kB array from bitarray import bitarray my bit array   bitarray 65536    32 kB my bit array setall 0  for N in four billion int array      if N    65536    bin num          my bit array N   65536    1 for i  bit in enumerate my bit array       if not bit          print bin num 65536   i         break

User · Answer

The simplest approach is to find the minimum number in the file  and return 1 less than that   This uses O 1  storage  and O n  time for a file of n numbers   However  it will fail if number range is limited  which could make min-1 not-a-number  The simple and straightforward method of using a bitmap has already been mentioned   That method uses O n  time and storage   A 2-pass method with 2 16 counting-buckets has also been mentioned   It reads 2 n integers  so uses O n  time and O 1  storage  but it cannot handle datasets with more than 2 16 numbers    However  it s easily extended to  eg  2 60 64-bit integers by running 4 passes instead of 2  and easily adapted to using tiny memory by using only as many bins as fit in memory and increasing the number of passes correspondingly  in which case run time is no longer O n  but instead is O n log n   The method of XOR ing all the numbers together  mentioned so far by rfrankel and at length by ircmaxell answers the question asked in stackoverflow 35185  as ltn100 pointed out   It uses O 1  storage and O n  run time   If for the moment we assume 32-bit integers  XOR has a 7  probability of producing a distinct number   Rationale  given   4G distinct numbers XOR d together  and ca  300M not in file  the number of set bits in each bit position has equal chance of being odd or even   Thus  2 32 numbers have equal likelihood of arising as the XOR result  of which 93  are already in file   Note that if the numbers in file aren t all distinct  the XOR method s probability of success rises

User · Answer

Just for the sake of completeness  here is another very simple solution  which will most likely take a very long time to run  but uses very little memory   Let all possible integers be the range from int min to int max  and bool isNotInFile integer  a function which returns true if the file does not contain a certain integer and false else  by comparing that certain integer with each integer in the file   for  integer i   int min  i  lt   int max    i        if  isNotInFile i             return i

User · Answer

Since the problem does not specify that we have to find the smallest possible number that is not in the file we could just generate a number that is longer than the input file itself

User · Answer

If we assume that the range of numbers will always be 2 n  an even power of 2   then exclusive-or will work  as shown by another poster    As far as why  let s prove it   The Theory  Given any 0 based range of integers that has 2 n elements with one element missing  you can find that missing element by simply xor-ing the known values together to yield the missing number   The Proof  Let s look at n   2   For n 2  we can represent 4 unique integers  0  1  2  3   They have a bit pattern of    0 - 00 1 - 01 2 - 10 3 - 11   Now  if we look  each and every bit is set exactly twice   Therefore  since it is set an even number of times  and exclusive-or of the numbers will yield 0   If a single number is missing  the exclusive-or will yield a number that when exclusive-ored with the missing number will result in 0   Therefore  the missing number  and the resulting exclusive-ored number are exactly the same   If we remove 2  the resulting xor will be 10  or 2    Now  let s look at n 1   Let s call the number of times each bit is set in n  x and the number of times each bit is set in n 1 y   The value of y will be equal to y   x   2 because there are x elements with the n 1 bit set to 0  and x elements with the n 1 bit set to 1   And since 2x will always be even  n 1 will always have each bit set an even number of times   Therefore  since n 2 works  and n 1 works  the xor method will work for all values of n gt  2    The Algorithm For 0 Based Ranges  This is quite simple   It uses 2 n bits of memory  so for any range  lt   32  2 32 bit integers will work  ignoring any memory consumed by the file descriptor    And it makes a single pass of the file   long supplied   0  long result   0  while  supplied   read int from file          result   result   supplied    return result    The Algorithm For Arbitrary Based Ranges  This algorithm will work for ranges of any starting number to any ending number  as long as the total range is equal to 2 n     This basically re-bases the range to have the minimum at 0   But it does require 2 passes through the file  the first to grab the minimum  the second to compute the missing int    long supplied   0  long result   0  long offset   INT MAX  while  supplied   read int from file          if  supplied  lt  offset            offset   supplied          reset file pointer    while  supplied   read int from file          result   result    supplied - offset     return result   offset    Arbitrary Ranges  We can apply this modified method to a set of arbitrary ranges  since all ranges will cross a power of 2 n at least once   This works only if there is a single missing bit   It takes 2 passes of an unsorted file  but it will find the single missing number every time   long supplied   0  long result   0  long offset   INT MAX  long n   0  double temp  while  supplied   read int from file          if  supplied  lt  offset            offset   supplied          reset file pointer    while  supplied   read int from file          n        result   result    supplied - offset        We need to increment n one value so that we take care of the missing     int value n   while  n    1    0     n  amp   n - 1          result   result    n       return result   offset    Basically  re-bases the range around 0   Then  it counts the number of unsorted values to append as it computes the exclusive-or   Then  it adds 1 to the count of unsorted values to take care of the missing value  count the missing one    Then  keep xoring the n value  incremented by 1 each time until n is a power of 2   The result is then re-based back to the original base   Done   Here s the algorithm I tested in PHP  using an array instead of a file  but same concept    function find  array         offset   min  array        n   0       result   0      foreach   array as  value             result    result     value -  offset            n               n       This takes care of the missing value     while   n    1    0      n  amp    n - 1               result    result     n               return  result    offset      Fed in an array with any range of values  I tested including negatives  with one inside that range which is missing  it found the correct value each time   Another Approach  Since we can use external sorting  why not just check for a gap   If we assume the file is sorted prior to the running of this algorithm   long supplied   0  long last   read int from file    while  supplied   read int from file          if  supplied    last   1            return last   1            last   supplied       The range is contiguous  so what do we do here   Let s return last   1  return last   1

User · Answer

For the 1 nbsp GB RAM variant you can use a bit vector  You need to allocate 4 billion bits    500 nbsp MB byte array  For each number you read from the input  set the corresponding bit to  1   Once you done  iterate over the bits  find the first one that is still  0   Its index is the answer

User · Answer

Statistically informed algorithms solve this problem using fewer passes than deterministic approaches   If very large integers are allowed then one can generate a number that is likely to be unique in O 1  time   A pseudo-random 128-bit integer like a GUID will only collide with one of the existing four billion integers in the set in less than one out of every 64 billion billion billion cases   If integers are limited to 32 bits then one can generate a number that is likely to be unique in a single pass using much less than 10 nbsp MB  The odds that a pseudo-random 32-bit integer will collide with one of the 4 billion existing integers is about 93   4e9   2 32    The odds that 1000 pseudo-random integers will all collide is less than one in 12 000 billion billion billion  odds-of-one-collision   1000   So if a program maintains a data structure containing 1000 pseudo-random candidates and iterates through the known integers  eliminating matches from the candidates  it is all but certain to find at least one integer that is not in the file

User · Answer

As Ryan said it basically  sort the file and then go over the integers and when a value is skipped there you have it     EDIT at downvoters  the OP mentioned that the file could be sorted so this is a valid method

User · Answer

Check the size of the input file  then output any number which is too large to be represented by a file that size  This may seem like a cheap trick  but it s a creative solution to an interview problem  it neatly sidesteps the memory issue  and it s technically O n    void maxNum ulong filesize        ulong bitcount   filesize   8    number of bits in file      for  ulong i   0  i  lt  bitcount  i                  Console Write 9             Should print 10 bitcount - 1  which will always be greater than 2 bitcount  Technically  the number you have to beat is 2 bitcount -  4   109 - 1   since you know there are  4 billion - 1  other integers in the file  and even with perfect compression they ll take up at least one bit each

User · Answer

If you don t assume the 32-bit constraint  just return a randomly generated 64-bit number  or 128-bit if you re a pessimist   The chance of collision is 1 in 2 64  4 10 9    4611686018 4  roughly 1 in 4 billion   You d be right most of the time    Joking    kind of

User · Answer

Based on the current wording in the original question  the simplest solution is   Find the maximum value in the file  then add 1 to it

User · Answer

As long as we re doing creative answers  here is another one   Use the external sort program to sort the input file numerically  This will work for any amount of memory you may have  it will use file storage if needed   Read through the sorted file and output the first number that is missing

User · Answer

I will answer the 1 nbsp GB version   There is not enough information in the question  so I will state some assumptions first   The integer is 32 bits with range -2 147 483 648 to 2 147 483 647   Pseudo-code   var bitArray   new bit 4294967296       0 5 GB  initialized to all 0s   foreach  var number in file        bitArray number   2147483648    1       Shift all numbers so they start at 0     for  var i   0  i  lt  4294967296  i          if  bitArray i     0            return i - 2147483648

User · Answer

Bit Elimination  One way is to eliminate bits  however this might not actually yield a result  chances are it won t   Psuedocode   long val   0xFFFFFFFFFFFFFFFF      all bits set  foreach long fileVal in file       val   val  amp   fileVal      if  val    0  error      Bit Counts  Keep track of the bit counts  and use the bits with the least amounts to generate a value  Again this has no guarantee of generating a correct value   Range Logic  Keep track of a list ordered ranges  ordered by start   A range is defined by the structure   struct Range     long Start  End     Inclusive    Range startRange   new Range   Start   0x0  End   0xFFFFFFFFFFFFFFFF      Go through each value in the file and try and remove it from the current range  This method has no memory guarantees  but it should do pretty well

User · Answer

Use a BitSet  4 billion integers  assuming up to 2 32 integers  packed into a BitSet at 8 per byte is 2 32   2 3   2 29   approx 0 5 Gb   To add a bit more detail - every time you read a number  set the corresponding bit in the BitSet  Then  do a pass over the BitSet to find the first number that s not present  In fact  you could do this just as effectively by repeatedly picking a random number and testing if it s present   Actually BitSet nextClearBit 0  will tell you the first non-set bit   Looking at the BitSet API  it appears to only support 0  MAX INT  so you may need 2 BitSets - one for   ve numbers and one for - ve numbers - but the memory requirements don t change

User · Answer

2128 1018   1   which is  28 16 1018   1   - cannot it be a universal answer for today  This represents a number that cannot be held in 16 EB file  which is the maximum file size in any current file system

User · Answer

If you have one integer missing from the range  0  2 x - 1  then just xor them all together   For example    gt  gt  gt  0   1   3 2  gt  gt  gt  0   1   2   3   4   6   7 5    I know this doesn t answer the question exactly  but it s a good answer to a very similar question

User · Answer

I may be reading this too closely  but the questions says  generate an integer which is not contained in the file    I d just sort the list and add 1 to the max entry   Bam  an integer which is not contained in the file

User · Answer

I think this is a solved problem  see above   but there s an interesting side case to keep in mind because it might get asked   If there are exactly 4 294 967 295  2 32 - 1  32-bit integers with no repeats  and therefore only one is missing  there is a simple solution   Start a running total at zero  and for each integer in the file  add that integer with 32-bit overflow  effectively  runningTotal    runningTotal   nextInteger    4294967296    Once complete  add 4294967296 2 to the running total  again with 32-bit overflow   Subtract this from 4294967296  and the result is the missing integer   The  only one missing integer  problem is solvable with only one run  and only 64 bits of RAM dedicated to the data  32 for the running total  32 to read in the next integer    Corollary   The more general specification is extremely simple to match if we aren t concerned with how many bits the integer result must have   We just generate a big enough integer that it cannot be contained in the file we re given   Again  this takes up absolutely minimal RAM   See the pseudocode     Grab the file size fseek fp  0L  SEEK END   sz   ftell fp     Print a  2  for every bit of the file  for  c 0  c lt sz  c        for  b 0  b lt 4  b          print  2

User · Answer

For some reason  as soon as I read this problem I thought of diagonalization   I m assuming arbitrarily large integers   Read the first number  Left-pad it with zero bits until you have 4 billion bits   If the first  high-order  bit is 0  output 1  else output 0   You don t really have to left-pad  you just output a 1 if there are not enough bits in the number   Do the same with the second number  except use its second bit   Continue through the file in this way   You will output a 4-billion bit number one bit at a time  and that number will not be the same as any in the file   Proof  it were the same as the nth number  then they would agree on the nth bit  but they don t by construction

User · Answer

You don t need to sort them   just repeatedly partition subsets of them   The first step is like the first pass of a quicksort   Pick one of the integers  x   and using it make a pass through the array to put all the values less than x to its left and values more than x to its right   Find which side of x has the greatest number of available slots  integers not in the list    This is easily computable by comparing the value of x with its position  Then repeat the partition on the sub-list on that side of x   Then repeat the partition on the sub-sub list with the greatest number of available integers   etc   Total number of compares to get down to an empty range should be about 4 billion  give or take

User · Answer

They may be looking to see if you have heard of a probabilistic Bloom Filter which can very efficiently determine absolutely if a value is not part of a large set   but can only determine with high probability it is a member of the set

User · Answer

For the 10 MB memory constraint    Convert the number to its binary representation  Create a binary tree where left   0 and right   1  Insert each number in the tree using its binary representation  If a number has already been inserted  the leafs will already have been created    When finished  just take a path that has not been created before to create the requested number   4 billion number   2 32  meaning 10 MB might not be sufficient   EDIT  An optimization is possible  if two ends leafs have been created and have a common parent  then they can be removed and the parent flagged as not a solution  This cuts branches and reduces the need for memory   EDIT II  There is no need to build the tree completely too  You only need to build deep branches if numbers are similar  If we cut branches too  then this solution might work in fact

User · Answer

EDIT Ok  this wasn t quite thought through as it assumes the integers in the file follow some static distribution  Apparently they don t need to  but even then one should try this     There are   4 3 billion 32-bit integers  We don t know how they are distributed in the file  but the worst case is the one with the highest Shannon entropy  an equal distribution  In this case  the probablity for any one integer to not occur in the file is     2    -1  2      4                          4  The lower the Shannon entropy  the higher this probability gets on the average  but even for this worst case we have a chance of 90  to find a nonoccurring number after 5 guesses with random integers  Just create such numbers with a pseudorandom generator  store them in a list  Then read int after int and compare it to all of your guesses  When there s a match  remove this list entry  After having been through all of the file  chances are you will have more than one guess left  Use any of them  In the rare  10  even at worst case  event of no guess remaining  get a new set of random integers  perhaps more this time  10- 99     Memory consumption  a few dozen bytes  complexity  O n   overhead  neclectable as most of the time will be spent in the unavoidable hard disk accesses rather than comparing ints anyway   The actual worst case  when we do not assume a static distribution  is that every integer occurs max  once  because then only 1 - 4000000000 2        6  of all integers don t occur in the file  So you ll need some more guesses  but that still won t cost hurtful amounts of memory

User · Answer

Trick question  unless it s been quoted improperly  Just read through the file once to get the maximum integer n  and return n 1   Of course you d need a backup plan in case n 1 causes an integer overflow

User · Answer

Old question  but I wonder about the  non-functional  requirements  In my opinion there should be a clue given - if this question was asked someplace else than in a book which then goes on to discuss all the possibilities with pros and cons  Often enough it seems to be askes in job interviews  leaving me puzzled as there can t be a definite answer given without knowing the soft requirements  i e   it must be very fast to lookup missing numbers  because it s used x times in a second    I think such question might be possible to give a reasonable answer for    I d merge-sort all numbers into a new file  using 4 byte per int  Of course this will be slow to do at first  But it can be done with small memory amount  you don t need to necessarily keep all in RAM  Use binary-search to check if the number exists n the presorted file  Since we remain 4-bytes per value this is no problem   disadvantages    File size Slow first sort - but only needed once   advantages    very quick to lookup   So again  a very nice question for a book  But I think it s an odd question when asking for a single best solution  when the problem to be solved isn t fully known

User · Answer

You could speed up finding the missing integers after reading the existing ones by storing ranges of unvisited integers in some tree structure   You d start by storing  0  4294967295  and every time you read an integer you splice the range it falls in  deleting a range when it becomes empty  At the end you have the exact set of integers that are missing in the ranges  So if you see 5 as the first integer  you d have  0  4  and  6  4294967295    This is a lot slower than marking bits so it would only be a solution for the 10MB case provided you can store the lower levels of the tree in files   One way to store such a tree would be a B-tree with the start of the range as the key and the end of the range as the value  Worst case usage would be when you get all odd or even integers which would mean storing 2 31 values or tens of GB for the tree    Ouch  Best case is a sorted file where you d only use a few integers for the whole tree   So not really the correct answer but I thought I d mention this way of doing it  I suppose I d fail the interview  -

User · Answer

Given an input file with four billion integers  provide an algorithm     to generate an integer which is not contained in the file  Assume you     have 1 GiB memory  Follow up with what you would do if you have only     10 MiB of memory          The size of the file is 4   109   4 bytes   16 GiB   In case of 32-bit Unsigned Integer  0  lt   Number  lt  2 32 0  lt   Number  lt  4 294 967 296   My proposed solution  C   without error checking   include  lt vector gt   include  lt fstream gt   include  lt iostream gt  using namespace std   int main          const long SIZE   1L  lt  lt  32       std  vector lt bool gt  checker SIZE  false        std  ifstream infile  file txt        TODO  error checking      unsigned int num   0       while  infile  gt  gt  num                checker num    true              infile close            print missing numbers      for  long i   0  i  lt  SIZE  i                  if   checker i               cout  lt  lt  i  lt  lt  endl              return 0      Complexity   Space   232 bits   229 Bytes   219 KB   29 MB   1 2 GB Time   Single Pass Completeness   Yes

User · Answer

Perhaps I m completely missing the point of this question  but you want to find an integer missing from a sorted file of integers   Uhh    really  Let s think about what such a file would look like   1 2 3 4 5 6     first missing number     etc   The solution to this problem seems trivial

User · Answer

I came up with the following algorithm   My idea  go through all the whole file of integers once and for every bit position count its 0s and 1s  The amount of 0s and 1s must be 2  numOfBits  2  therefore  if the amount is less then expected we can use it of our resulting number   For example  suppose integer is 32 bit  then we require  int   ones   new int 32   int   zeroes   new int 32     For every number we have to iterate though 32 bits and increase value of 0 or 1   for int i   0  i  lt  32  i        ones i      val gt  gt i amp 0x1       zeroes i      val gt  gt i amp 0x1   1 0 1      Finally  after the file was processed   int res   0  for int i   0  i  lt  32  i        if ones i   lt   long 1 lt  lt 31 res  1 lt  lt i    return res    NOTE  in some languages  ex  Java  1 lt  lt 31 is a negative number  therefore   long 1 lt  lt 31 is the right way to do it

User · Answer

Why make it so complicated  You ask for an integer not present in the file   According to the rules specified  the only thing you need to store is the largest integer that you encountered so far in the file  Once the entire file has been read  return a number 1 greater than that   There is no risk of hitting maxint or anything  because according to the rules  there is no restriction to the size of the integer or the number returned by the algorithm

User · Answer

A detailed discussion on this problem has been discussed in Jon Bentley  Column 1  Cracking the Oyster  Programming Pearls Addison-Wesley pp 3-10  Bentley discusses several approaches  including external sort  Merge Sort using several external files etc   But the best method Bentley suggests is a single pass algorithm using bit fields  which he humorously calls  Wonder Sort     Coming to the problem  4 billion numbers can be represented in    4 billion bits    4000000000   8  bytes   about 0 466 GB   The code to implement the bitset is simple   taken from solutions page     define BITSPERWORD 32  define SHIFT 5  define MASK 0x1F  define N 10000000 int a 1   N BITSPERWORD    void set int i           a i gt  gt SHIFT       1 lt  lt  i  amp  MASK      void clr int i           a i gt  gt SHIFT   amp     1 lt  lt  i  amp  MASK      int  test int i   return a i gt  gt SHIFT   amp     1 lt  lt  i  amp  MASK        Bentley s algorithm makes a single pass over the file  setting the appropriate bit in the array and then examines this array using test macro above to find the missing number   If the available memory is less than 0 466 GB  Bentley suggests a k-pass algorithm  which divides the input into ranges depending on available memory  To take a very simple example  if only 1 byte  i e memory to handle 8 numbers   was available and the range was from 0 to 31  we divide this into ranges of 0 to 7  8-15  16-22 and so on and handle this range in each of 32 8   4 passes   HTH

[algorithm] Generate an integer that is not among four billion given ones

Examples related to algorithm

Examples related to file

Examples related to search

Examples related to out-of-memory

Examples related to memory-limit