Encuentre un entero no entre los cuatro mil millones dados

Es una pregunta de entrevista:

Dado un archivo de entrada con cuatro mil millones de enteros, proporcione un algoritmo para generar un entero que no esté contenido en el archivo. Supongamos que tiene 1 GB de memoria. Haga un seguimiento con lo que haría si solo tiene 10 MB de memoria.

Mi análisis:

El tamaño del archivo es 4 × 10 9 × 4 bytes = 16 GB.

Podemos hacer una clasificación externa, así podemos conocer el rango de los enteros. Mi pregunta es ¿cuál es la mejor forma de detectar el entero faltante en los conjuntos de enteros grandes ordenados?

Mi comprensión (después de leer todas las respuestas):

Suponiendo que estamos hablando de enteros de 32 bits. Hay 2 ^ 32 = 4 * 10 9 enteros distintos.

Caso 1: tenemos 1 GB = 1 * 10 9 * 8 bits = 8 billones de bits de memoria. Solución: si usamos un bit que representa un entero distinto, es suficiente. no necesitamos ordenar Implementación:

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 << (n%radix)); } for(int i = 0; i< bitfield.lenght; i++){ for(int j =0; j<radix; j++){ if( (bitfield[i] & (1<<j)) == 0) System.out.print(i*radix+j); } } } 

Caso 2: 10 MB de memoria = 10 * 10 6 * 8 bits = 80 millones de bits

 Solution: For all possible 16-bit prefixes, there are 2^16 number of integers = 65536, we need 2^16 * 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. step1: Build the counter of each bucket through the first pass through the file. step2: Scan the buckets, find the first one who has less than 65536 hit. step3: Build new buckets whose high 16-bit prefixes are we found in step2 through second pass of the file step4: Scan the buckets built in step3, find the first bucket which doesnt have a hit. The code is very similar to above one. 

Conclusión: disminuimos la memoria al boost el pase de archivos.


Una aclaración para los que llegan tarde: la pregunta, como se le preguntó, no dice que hay exactamente un entero que no está contenido en el archivo, al menos no es así como la mayoría de las personas lo interpretan. Sin embargo, muchos comentarios en el hilo de comentarios se refieren a esa variación de la tarea. Lamentablemente, el comentario que lo introdujo en el hilo de comentarios fue eliminado por su autor, por lo que ahora parece que las respuestas huérfanas simplemente lo malinterpretaron. Es muy confuso Lo siento.

Suponiendo que “entero” signifique 32 bits : tener 10 MB de espacio es más que suficiente para contar cuántos números hay en el archivo de entrada con un prefijo de 16 bits dado, para todos los posibles prefijos de 16 bits en un pase el archivo de entrada. Al menos uno de los cubos habrá sido golpeado menos de 2 ^ 16 veces. Haga una segunda pasada para averiguar cuál de los posibles números en ese cubo ya se usa.

Si esto significa más de 32 bits, pero aún de tamaño limitado : haga lo anterior, ignorando todos los números de entrada que se encuentren fuera del rango de 32 bits (firmado o no, su elección).

Si “entero” significa número entero matemático : lea la entrada una vez y realice un seguimiento de la longitud de número más grande del número más largo que jamás haya visto. Cuando hayas terminado, muestra el máximo más uno un número aleatorio que tiene un dígito más. (Uno de los números en el archivo puede ser un bignum que requiere más de 10 MB para representar exactamente, pero si la entrada es un archivo, entonces puede representar al menos la longitud de cualquier elemento que encaje en él).

Los algoritmos informados estadísticamente resuelven este problema usando menos pases que los enfoques deterministas.

Si se permiten números enteros muy grandes, entonces uno puede generar un número que probablemente sea único en el tiempo O (1). Un entero pseudoaleatorio de 128 bits como un GUID solo colisionará con uno de los cuatro mil millones de enteros existentes en el conjunto en menos de uno de cada 64 mil millones de billones de casos.

Si los números enteros están limitados a 32 bits, entonces uno puede generar un número que probablemente sea único en un solo pase utilizando mucho menos de 10 MB. Las probabilidades de que un entero pseudoaleatorio de 32 bits colisione con uno de los 4 mil millones de enteros existentes es aproximadamente 93% (4e9 / 2 ^ 32). La probabilidad de que 1000 enteros pseudoaleatorios colisionen es menos de uno en 12,000 billones de billones (odds-of-one-collision ^ 1000). Entonces, si un progtwig mantiene una estructura de datos que contiene 1000 candidatos pseudoaleatorios y recorre los enteros conocidos, eliminando las coincidencias de los candidatos, es casi seguro que encontrará al menos un entero que no está en el archivo.

Una discusión detallada sobre este problema ha sido discutida en Jon Bentley “Columna 1. Cracking the Oyster” Programming Pearls Addison-Wesley pp.3-10

Bentley sugiere varios enfoques, incluido el ordenamiento externo, Merge Sort utilizando varios archivos externos, etc., pero el mejor método que sugiere Bentley es un algoritmo de paso único que utiliza campos de bits , que llama humorísticamente “Wonder Sort”. Llegando al problema, 4 mil millones los números pueden ser representados en:

 4 billion bits = (4000000000 / 8) bytes = about 0.466 GB 

El código para implementar el conjunto de bits es simple: (tomado de la página de soluciones )

 #define BITSPERWORD 32 #define SHIFT 5 #define MASK 0x1F #define N 10000000 int a[1 + N/BITSPERWORD]; void set(int i) { a[i>>SHIFT] |= (1< <(i & MASK)); } void clr(int i) { a[i>>SHIFT] &= ~(1< <(i & MASK)); } int test(int i){ return a[i>>SHIFT] & (1< <(i & MASK)); } 

El algoritmo de Bentley hace una sola pasada sobre el archivo, set el bit apropiado en la matriz y luego examina esta matriz usando la macro de test arriba para encontrar el número que falta.

Si la memoria disponible es menor a 0.466 GB, Bentley sugiere un algoritmo k-pass, que divide la entrada en rangos dependiendo de la memoria disponible. Para tomar un ejemplo muy simple, si solo estaba disponible 1 byte (es decir, memoria para manejar 8 números) y el rango era de 0 a 31, lo dividimos en rangos de 0 a 7, 8-15, 16-22 y así sucesivamente y manejar este rango en cada uno de 32/8 = 4 pases.

HTH.

Como el problema no especifica que tenemos que encontrar el número más pequeño posible que no está en el archivo, podríamos generar un número que sea más largo que el archivo de entrada en sí. 🙂

Para la variante de RAM de 1 GB puede usar un vector de bits. Debe asignar 4 mil millones de bits == 500 MB de matriz de bytes. Para cada número que lea desde la entrada, ajuste el bit correspondiente a ‘1’. Una vez que lo hayas hecho, itera sobre los bits, encuentra el primero que todavía es ‘0’. Su índice es la respuesta.

Si son enteros de 32 bits (probablemente por la elección de ~ 4 mil millones de números cerca de 2 ^ 32), su lista de 4 mil millones de números ocupará como máximo el 93% de los enteros posibles (4 * 10 ^ 9 / (2) ^ 32)). Por lo tanto, si crea una matriz de bits de 2 ^ 32 bits con cada bit inicializado en cero (que ocupará 2 ^ 29 bytes ~ 500 MB de RAM, recuerde un byte = 2 ^ 3 bits = 8 bits), lea atentamente lista de enteros y para cada int establece el elemento de matriz de bits correspondiente de 0 a 1; y luego lee tu matriz de bits y devuelve el primer bit que sigue siendo 0.

En el caso de que tenga menos RAM (~ 10 MB), esta solución debe modificarse ligeramente. 10 MB ~ 83886080 bits es aún suficiente para hacer una matriz de bits para todos los números entre 0 y 83886079. Así que podría leer su lista de entradas; y solo grabe #s que están entre 0 y 83886079 en su matriz de bits. Si los números se distribuyen al azar; con una probabilidad abrumadora (difiere en un 100% en alrededor de 10 ^ -2592069 ) encontrará una int faltante). De hecho, si solo elige los números del 1 al 2048 (con solo 256 bytes de RAM), igual encontrará un porcentaje que falta (un porcentaje abrumador (99.99999999999999999999999999999999999999999999999999999999999995%) del tiempo.

Pero digamos que en lugar de tener alrededor de 4 mil millones de números; tenía algo así como 2 ^ 32 – 1 números y menos de 10 MB de RAM; por lo que cualquier rango pequeño de ints solo tiene una pequeña posibilidad de no contener el número.

Si tuviera garantizado que cada int en la lista fuera único, podría sumr los números y restar la sum con un # faltante a la sum completa (1/2) (2 ^ 32) (2 ^ 32 – 1) = 9223372034707292160 a encuentra la falta int. Sin embargo, si un int se produjo dos veces, este método fallará.

Sin embargo, siempre puedes dividir y conquistar. Un método ingenuo sería leer a través de la matriz y contar el número de números que están en la primera mitad (0 a 2 ^ 31-1) y la segunda mitad (2 ^ 31, 2 ^ 32). Luego elige el rango con menos números y repite dividir ese rango por la mitad. (Digamos que si hubiera dos números menos en (2 ^ 31, 2 ^ 32) su próxima búsqueda contaría los números en el rango (2 ^ 31, 3 * 2 ^ 30-1), (3 * 2 ^ 30, 2 ^ 32). Sigue repitiendo hasta que encuentres un rango con cero números y tengas tu respuesta. Deberías tomar O (lg N) ~ 32 lecturas a través de la matriz.

Ese método fue ineficiente. Solo estamos usando dos enteros en cada paso (o aproximadamente 8 bytes de RAM con un entero de 4 bytes (32 bits)). Un mejor método sería dividir en sqrt (2 ^ 32) = 2 ^ 16 = 65536 bins, cada uno con 65536 números en un bin. Cada contenedor requiere 4 bytes para almacenar su conteo, por lo que necesita 2 ^ 18 bytes = 256 kB. Entonces bin 0 es (0 a 65535 = 2 ^ 16-1), bin 1 es (2 ^ 16 = 65536 a 2 * 2 ^ 16-1 = 131071), bin 2 es (2 * 2 ^ 16 = 131072 a 3 * 2 ^ 16-1 = 196607). En Python tendrías algo así como:

 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 < 65536: break # we have found an incomplete bin with missing ints (bin_num) 

Lea la lista de enteros de ~ 4 mil millones; y cuente cuántas casillas caen en cada uno de los 2 ^ 16 bandejas y encuentre un incomplete_bin que no tenga todos los 65536 números. Luego, vuelve a leer la lista de 4 mil millones de enteros; pero esta vez solo notamos cuando los enteros están en ese rango; volteando un poco cuando los encuentres.

 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 

¿Por qué hacerlo tan complicado? Usted pregunta por un entero que no está presente en el archivo?

De acuerdo con las reglas especificadas, lo único que necesita almacenar es el entero más grande que encontró hasta ahora en el archivo. Una vez que se haya leído el archivo completo, devuelva un número 1 mayor que ese.

No hay riesgo de golpear maxint o cualquier cosa, porque de acuerdo con las reglas, no hay ninguna restricción para el tamaño del número entero o el número devuelto por el algoritmo.

Esto se puede resolver en muy poco espacio usando una variante de búsqueda binaria.

  1. Comience con el rango permitido de números, 0 a 4294967295 .

  2. Calcule el punto medio.

  3. Pasa por el archivo, contando cuántos números eran iguales, menores o más altos que el valor del punto medio.

  4. Si no hay números iguales, terminaste. El número de punto medio es la respuesta.

  5. De lo contrario, elija el rango que tenga el menor número y repita desde el paso 2 con este nuevo rango.

Esto requerirá hasta 32 escaneos lineales a través del archivo, pero solo usará unos pocos bytes de memoria para almacenar el rango y los conteos.

Esto es esencialmente lo mismo que la solución de Henning , excepto que usa dos contenedores en lugar de 16k.

EDITAR Ok, esto no fue muy bien pensado ya que supone que los enteros en el archivo siguen una distribución estática. Aparentemente no es necesario, pero aun así uno debería intentar esto:


Hay inte4.3 mil millones de enteros de 32 bits. No sabemos cómo se distribuyen en el archivo, pero el peor caso es el que tiene la más alta entropía de Shannon: una distribución igual. En este caso, la probabilidad de que un entero no ocurra en el archivo es

((2³²-1) / 2³²) ⁴ ⁰⁰⁰ ⁰⁰⁰ 4 ≈ .4

Cuanto menor es la entropía de Shannon, mayor es la probabilidad en promedio, pero incluso en este peor caso, tenemos una probabilidad del 90% de encontrar un número no recurrente después de 5 conjeturas con enteros aleatorios. Simplemente cree esos números con un generador pseudoaleatorio, guárdelos en una lista. Luego lea int después de int y compárelo con todas sus suposiciones. Cuando hay una coincidencia, elimine esta entrada de la lista. Después de haber revisado todo el archivo, es probable que te quede más de una estimación. Usa cualquiera de ellos. En el caso raro (10% incluso en el peor de los casos) de que no quede ninguna conjetura, obtenga un nuevo conjunto de enteros aleatorios, tal vez más esta vez (10-> 99%).

Consumo de memoria: algunas docenas de bytes, complejidad: O (n), sobrecarga: neclectable, ya que la mayor parte del tiempo se utilizará en los inevitables accesos al disco duro en lugar de compararlos de todos modos.


El peor caso real, cuando no suponemos una distribución estática, es que cada entero se produce como máximo. una vez, porque entonces solo 1 – 4000000000 / 2³² ≈ 6% de todos los enteros no ocurren en el archivo. Por lo tanto, necesitará algunas suposiciones más, pero eso no costará cantidades hirientes de memoria.

Si tiene un entero que falta en el rango [0, 2 ^ x – 1], simplemente júntelos todos juntos. Por ejemplo:

 >>> 0 ^ 1 ^ 3 2 >>> 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 6 ^ 7 5 

(Sé que esto no responde exactamente la pregunta, pero es una buena respuesta a una pregunta muy similar).

Según la redacción actual en la pregunta original, la solución más simple es:

Encuentre el valor máximo en el archivo, luego agregue 1 a él.

Pueden estar buscando si ha oído hablar de un Filtro de Floración probabilístico que puede determinar de manera muy eficiente absolutamente si un valor no es parte de un conjunto grande, (pero solo puede determinar con alta probabilidad que es un miembro del conjunto).

Use un BitSet . 4 billones enteros (suponiendo hasta 2 ^ 32 enteros) empaquetados en un BitSet a 8 por byte es 2 ^ 32/2 ^ 3 = 2 ^ 29 = aproximadamente 0.5 Gb.

Para agregar un poco más de detalle, cada vez que lea un número, configure el bit correspondiente en el BitSet. Luego, pase sobre el BitSet para encontrar el primer número que no está presente. De hecho, puede hacer esto con la misma eficacia seleccionando repetidamente un número aleatorio y probando si está presente.

En realidad, BitSet.nextClearBit (0) le dirá el primer bit no establecido.

Al observar la API BitSet, parece que solo es compatible con 0..MAX_INT, por lo que puede necesitar 2 BitSets, uno para más números y otro para números, pero los requisitos de memoria no cambian.

Si no hay límite de tamaño, la forma más rápida es tomar la longitud del archivo y generar la longitud del archivo + 1 número de dígitos aleatorios (o solo “11111 …” s). Ventaja: ni siquiera necesita leer el archivo, y puede minimizar el uso de la memoria casi a cero. Desventaja: Imprimirá miles de millones de dígitos.

Sin embargo, si el único factor fue minimizar el uso de la memoria, y nada más es importante, esta sería la solución óptima. Incluso podría obtener un premio por “el peor abuso de las reglas”.

Si suponemos que el rango de números siempre será 2 ^ n (un poder par de 2), entonces exclusivo o funcionará (como se muestra en otro póster). En cuanto a por qué, demostrémoslo:

La teoría

Dado cualquier rango 0 de enteros que tiene 2^n elementos con un elemento faltante, puede encontrar ese elemento faltante simplemente combinando los valores conocidos para obtener el número que falta.

La prueba

Miremos n = 2. Para n = 2, podemos representar 4 enteros únicos: 0, 1, 2, 3. Tienen un patrón de bits de:

  • 0 – 00
  • 1 – 01
  • 2 – 10
  • 3 – 11

Ahora, si miramos, cada bit se establece exactamente dos veces. Por lo tanto, dado que se establece un número par de veces, y exclusivo (o de los números rendirá 0. Si falta un número único, el exclusivo) o producirá un número que cuando esté exclusivo con el número que falta dará como resultado 0. Por lo tanto, el número que falta y el número resultante de exclusividad son exactamente los mismos. Si eliminamos 2, el xor resultante será 10 (o 2).

Ahora, veamos n + 1. Llamemos a la cantidad de veces que cada bit se establece en n , x la cantidad de veces que cada bit se establece en n+1 y . El valor de y será igual a y = x * 2 porque hay x elementos con el n+1 bit establecido en 0, y x elementos con el n+1 bit establecido en 1. Y dado que 2x siempre será par, n+1 siempre tendrá cada bit establecido un número par de veces.

Por lo tanto, dado que n=2 funciona, y n+1 funciona, el método xor funcionará para todos los valores de n>=2 .

El algoritmo para rangos basados ​​en 0

Esto es bastante simple. Utiliza 2 * n bits de memoria, por lo que para cualquier rango < = 32, 2 enteros de 32 bits funcionarán (ignorando cualquier memoria consumida por el descriptor del archivo). Y hace una sola pasada del archivo.

 long supplied = 0; long result = 0; while (supplied = read_int_from_file()) { result = result ^ supplied; } return result; 

El algoritmo para rangos basados ​​en arbitrarios

Este algoritmo funcionará para rangos de cualquier número inicial a cualquier número final, siempre y cuando el rango total sea 2 ^ n … Esto básicamente vuelve a basar el rango para tener el mínimo en 0. Pero requiere 2 pases a través del archivo (el primero en tomar el mínimo, el segundo para calcular el int faltante).

 long supplied = 0; long result = 0; long offset = INT_MAX; while (supplied = read_int_from_file()) { if (supplied < 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 < 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 & (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. Hecho.

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 & ($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; 

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 < 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 * 10 9 - 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.

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.

  • 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.

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.

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.

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 < = int_max; ++i) { if (isNotInFile(i)) { return i; } } 

For the 10 MB memory constraint:

  1. Convert the number to its binary representation.
  2. Create a binary tree where left = 0 and right = 1.
  3. Insert each number in the tree using its binary representation.
  4. 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.

EDITAR

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.

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.

I will answer the 1 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-código:

 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 < 4294967296; i++) { if (bitArray[i] == 0) { return i - 2147483648; } } 

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 & ~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.

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.

2 128*10 18 + 1 ( which is (2 8 ) 16*10 18 + 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.

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 

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.

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.)