Me han dado esta 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. Suponga que tiene 1 GB de memoria. Haga un seguimiento de lo que haría si tuviera solo 10 MB de memoria.

Mi analisis:

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

Podemos hacer una ordenación externa, lo que nos permite conocer el rango de los enteros.

Mi pregunta es ¿cuál es la mejor manera de detectar el entero que falta en los conjuntos de enteros grandes ordenados?

Mi entendimiento (después de leer todas las respuestas):

Suponiendo que estamos hablando de enteros de 32 bits, hay 2 ³² = 4 * 10 ⁹ enteros distintos.

Caso 1: tenemos 1 GB = 1 * 10 ⁹ * 8 bits = memoria de 8 mil millones de bits.

Solución:

Si usamos un bit que representa un número 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 ⁶ * 8 bits = 80 millones de bits

Solución:

Para todos los posibles prefijos de 16 bits, hay 2 ¹⁶ número de enteros = 65536, necesitamos 2 ¹⁶ * 4 * 8 = 2 millones de bits. Necesitamos construir 65536 cubos. Para cada segmento, necesitamos 4 bytes que contengan todas las posibilidades porque el peor de los casos es que todos los 4 mil millones de enteros pertenecen al mismo segmento.

1. Construya el contador de cada cubo a través de la primera pasada a través del archivo.
2. Escanee los cubos, encuentre el primero que tenga menos de 65536 golpes.
3. Cree nuevos cubos cuyos altos prefijos de 16 bits se encuentran en el paso 2 al segundo paso del archivo
4. Escanee los cubos construidos en el paso 3, encuentre el primer cubo que no tenga éxito.

El código es muy similar al anterior.

Conclusión: disminuimos la memoria al aumentar el paso del archivo.

^{Una aclaración para quienes llegan tarde: la pregunta, como se hizo, no dice que haya exactamente un número entero que no esté contenido en el archivo, al menos esa no es la forma en que la mayoría de las personas lo interpreta. Sin embargo, muchos comentarios en el hilo de comentarios son sobre esa variación de la tarea. Desafortunadamente, el comentario que lo introdujo en el hilo de comentarios fue eliminado más tarde por su autor, por lo que ahora parece que las respuestas huérfanas simplemente lo malinterpretaron todo. Es muy confuso, lo siento.}

Suponiendo que "entero" significa 32 bits : 10 MB de espacio es más que suficiente para contar cuántos números hay en el archivo de entrada con cualquier prefijo de 16 bits dado, para todos los posibles prefijos de 16 bits en una pasada a través del fichero de entrada. Al menos uno de los cubos habrá sido golpeado menos de 2 ¹⁶ veces. Haga un segundo pase para encontrar cuál de los números posibles en ese cubo ya se usa.

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

Si "entero" significa entero matemático : lea la entrada una vez y realice un seguimiento de la longitud del número más grande del número más largo que haya visto. Cuando haya terminado, envíe el máximo más uno un número aleatorio que tenga 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 representarse exactamente, pero si la entrada es un archivo, entonces al menos puede representar la longitud de cualquier cosa que quepa en él).

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

Si se permiten enteros muy grandes, se 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 billones de enteros existentes en el conjunto en menos de uno de cada 64 billones de billones de casos.

Si los enteros están limitados a 32 bits , se puede generar un número que probablemente sea único en una sola pasada utilizando mucho menos de 10 MB. Las probabilidades de que un entero de 32 bits pseudoaleatorio choque con uno de los 4 mil millones de enteros existentes es de aproximadamente el 93% (4e9 / 2 ^ 32). La probabilidad de que 1000 enteros pseudoaleatorios colisionen es menor a uno en 12,000 billones de billones (probabilidad de colisión ^ 1000). Entonces, si un programa mantiene una estructura de datos que contiene 1000 candidatos pseudoaleatorios e itera a través de los enteros conocidos, eliminando coincidencias de los candidatos, es casi seguro encontrar al menos un entero que no esté en el archivo.

Una discusión detallada sobre este problema se ha discutido en Jon Bentley "Columna 1. Cracking the Oyster" Perlas de programación Addison-Wesley pp.3-10

Bentley analiza varios enfoques, incluida la ordenación externa, la ordenación por fusión utilizando varios archivos externos, etc., pero el mejor método que sugiere Bentley es un algoritmo de un solo paso que utilice campos de bits , que llama con humor "Wonder Sort" :) Llegando al problema, 4 mil millones los números se pueden representar 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 realiza una sola pasada sobre el archivo, setmarca el bit apropiado en la matriz y luego examina esta matriz usando la testmacro de arriba para encontrar el número que falta.

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

HTH

Dado que 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 1 GB de RAM, 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 de la entrada, establezca el bit correspondiente a '1'. Una vez que hayas terminado, itera sobre los bits, encuentra el primero que sigue siendo '0'. Su índice es la respuesta.

Si son enteros de 32 bits (probablemente de la elección de ~ 4 mil millones de números cercanos a 2 ³² ), su lista de 4 mil millones de números ocupará como máximo el 93% de los posibles enteros (4 * 10 ⁹ / (2 ³² ) ) Entonces, si crea una matriz de bits de 2 ³² bits bits con cada bit inicializado a cero (que ocupará 2 ²⁹ bytes ~ 500 MB de RAM; recuerde un byte = 2 ³ bits = 8 bits), lea su lista entera y para cada int establece el elemento de matriz de bits correspondiente de 0 a 1; y luego lea su matriz de bits y devuelva el primer bit que todavía es 0.

En el caso de que tenga menos RAM (~ 10 MB), esta solución debe modificarse ligeramente. 10 MB ~ 83886080 bits todavía son suficientes para hacer una matriz de bits para todos los números entre 0 y 83886079. Para que pueda leer su lista de entradas; y solo registre # 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 aproximadamente 10 ^-2592069 ) se encuentra un int que falta). De hecho, si solo elige los números del 1 al 2048 (con solo 256 bytes de RAM), todavía encontrará un número perdido en un porcentaje abrumador (99.99999999999999999999999999999999999999999999999999999999999995%) del tiempo.

Pero digamos en lugar de tener unos 4 mil millones de números; tenías algo así como 2 ³² - 1 números y menos de 10 MB de RAM; entonces cualquier rango pequeño de entradas solo tiene una pequeña posibilidad de no contener el número.

Si se le garantizó que cada int en la lista era único, podría sumar los números y restar la suma con un # faltante a la suma total (½) (2 ³² ) (2 ³² - 1) = 9223372034707292160 para encontrar el int faltante . Sin embargo, si se produjo un int dos veces, este método fallará.

Sin embargo, siempre puedes dividir y conquistar. Un método ingenuo sería leer la matriz y contar el número de números que están en la primera mitad (0 a 2 ³¹ -1) y la segunda mitad (2 ³¹ , 2 ³² ). Luego elija el rango con menos números y repita dividiendo ese rango a la mitad. (Diga si hubiera dos números menos en (2 ³¹ , 2 ³² ), entonces su próxima búsqueda contaría los números en el rango (2 ³¹ , 3 * 2 ³⁰ -1), (3 * 2 ³⁰ , 2 ³² ). repita hasta que encuentre un rango con números cero y tenga su respuesta. Debe 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 ³² ) = 2 ¹⁶ = 65536 contenedores, cada uno con 65536 números en un contenedor. Cada bin requiere 4 bytes para almacenar su recuento, por lo que necesita 2 ¹⁸ bytes = 256 kB. Entonces bin 0 es (0 a 65535 = 2 ¹⁶ -1), bin 1 es (2 ¹⁶ = 65536 a 2 * 2 ¹⁶ -1 = 131071), bin 2 es (2 * 2 ¹⁶ = 131072 a 3 * 2 ¹⁶ - 1 = 196607). En python tendrías algo 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 ~ 4 mil millones de enteros; y cuente cuántas entradas caen en cada uno de los 2 ¹⁶ contenedores y encuentre un incomplete_bin que no tenga todos los 65536 números. Luego lees la lista entera de 4 mil millones nuevamente; pero esta vez solo nota cuando los enteros están en ese rango; volteando un poco cuando los encuentras.

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? ¿Pides un número entero no presente en el archivo?

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

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

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

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

2. Calcule el punto medio.

3. Recorra el archivo, contando cuántos números fueron iguales, menores o mayores que el valor del punto medio.

4. Si no hay números iguales, ya está. El número del punto medio es la respuesta.

5. De lo contrario, elija el rango que tenga la menor cantidad de números 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 recuentos.

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

EDITAR Ok, esto no se pensó bien, ya que supone que los enteros en el archivo siguen alguna distribución estática. Aparentemente no necesitan hacerlo, pero incluso entonces uno debería intentar esto:

Hay ≈4.3 mil millones de enteros de 32 bits. No sabemos cómo se distribuyen en el archivo, pero el peor de los casos es el que tiene la mayor 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

Cuanto más baja es la entropía de Shannon, mayor es la probabilidad promedio, pero incluso en el peor de los casos, tenemos una probabilidad del 90% de encontrar un número no recurrente después de 5 suposiciones con enteros aleatorios. Simplemente cree dichos números con un generador pseudoaleatorio, guárdelos en una lista. Luego lea int tras int y compárelo con todas sus conjeturas. Cuando haya una coincidencia, elimine esta entrada de la lista. Después de haber revisado todo el archivo, es probable que le quede más de una suposició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: unas pocas docenas de bytes, complejidad: O (n), sobrecarga: desglosable, ya que la mayor parte del tiempo se dedicará a los inevitables accesos al disco duro en lugar de comparar ints de todos modos.

Si le falta un número entero del rango [0, 2 ^ x - 1], entonces simplemente póngalos a la vez. Por ejemplo:

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

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

Es posible que estén buscando ver si ha oído hablar de un filtro Bloom 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 si es miembro del conjunto).

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

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

Utilizar un BitSet . 4 billones de enteros (suponiendo hasta 2 ^ 32 enteros) empaquetados en un BitSet a 8 por byte son 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 BitSet para encontrar el primer número que no está presente. De hecho, podría 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 de BitSet, parece que solo admite 0..MAX_INT, por lo que puede necesitar 2 BitSets, uno para números + y cinco números for-have, 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 simplemente "11111 ..." s). Ventaja: ni siquiera necesita leer el archivo, y puede minimizar el uso de memoria casi a cero. Desventaja: imprimirá miles de millones de dígitos.

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

Si suponemos que el rango de números siempre será 2 ^ n (una potencia 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 de enteros basado en 0 que tenga 2^nelementos con un elemento faltante, puede encontrar ese elemento faltante simplemente haciendo un xoring de los valores conocidos para obtener el número faltante.

La prueba

Veamos 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 producirá 0. Si falta un solo número, el exclusivo-o producirá un número que cuando se ofrece exclusivo con el número faltante dará como resultado 0. Por lo tanto, el número faltante y el número exclusivo resultante son exactamente iguales. Si eliminamos 2, el xor resultante será10 (o 2).

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

Por lo tanto, dado que n=2funciona y n+1funciona, 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, funcionarán 2 enteros de 32 bits (ignorando cualquier memoria consumida por el descriptor de 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 arbitrarios

Este algoritmo funcionará para rangos de cualquier número inicial a cualquier número final, siempre que el rango total sea igual a 2 ^ n ... Esto básicamente re-basa el rango para tener el mínimo en 0. Pero requiere 2 pases a través del archivo (el primero para obtener 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;

Rangos arbitrarios

Podemos aplicar este método modificado a un conjunto de rangos arbitrarios, ya que todos los rangos cruzarán una potencia de 2 ^ n al menos una vez. Esto funciona solo si falta un bit. Se necesitan 2 pases de un archivo sin clasificar, pero encontrará el único número que falta cada vez:

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;

Básicamente, re-basa el rango alrededor de 0. Luego, cuenta el número de valores sin clasificar para agregar mientras calcula el exclusivo-o. Luego, agrega 1 al recuento de valores no ordenados para cuidar el valor faltante (cuente el valor faltante). Luego, siga xorreando el valor de n, incrementado en 1 cada vez hasta que n sea una potencia de 2. El resultado se vuelve a basar en la base original. Hecho.

Aquí está el algoritmo que probé en PHP (usando una matriz en lugar de un archivo, pero el mismo concepto):

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;
}

Alimentado en una matriz con cualquier rango de valores (probé incluyendo negativos) con uno dentro de ese rango que falta, encontró el valor correcto cada vez.

Otro enfoque

Dado que podemos usar la ordenación externa, ¿por qué no simplemente buscar una brecha? Si suponemos que el archivo está ordenado antes de ejecutar este algoritmo:

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;

Pregunta capciosa, a menos que se haya citado incorrectamente. Simplemente lea el archivo una vez para obtener el número entero máximo ny regrese n+1.

Por supuesto, necesitaría un plan de respaldo en caso de que se n+1produzca un desbordamiento de enteros.

Verifique el tamaño del archivo de entrada, luego envíe cualquier número que sea demasiado grande para ser representado por un archivo de ese tamaño. Esto puede parecer un truco barato, pero es una solución creativa para un problema de entrevista, evita el problema de memoria y técnicamente es 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);
    }
}

Debe imprimir 10 ^bitcount - 1 , que siempre será mayor que 2 ^bitcount . Técnicamente, el número que tiene que vencer es 2 ^bitcount - (4 * 10 ⁹ - 1) , ya que sabe que hay (4 mil millones - 1) otros enteros en el archivo, e incluso con una compresión perfecta ocuparán al menos un bit cada uno

• El enfoque más simple es encontrar el número mínimo en el archivo y devolver 1 menos que eso. Utiliza el almacenamiento O (1) y el tiempo O (n) para un archivo de n números. Sin embargo, fallará si el rango de números es limitado, lo que podría hacer que min-1 no sea un número.

• Ya se ha mencionado el método simple y directo de usar un mapa de bits. Ese método utiliza O (n) tiempo y almacenamiento.

• También se ha mencionado un método de 2 pasadas con 2 ^ 16 cubos de conteo. Lee 2 * n enteros, por lo que utiliza el tiempo O (n) y el almacenamiento O (1), pero no puede manejar conjuntos de datos con más de 2 ^ 16 números. Sin embargo, se extiende fácilmente a (p. Ej.) 2 ^ 60 enteros de 64 bits ejecutando 4 pases en lugar de 2, y se adapta fácilmente para usar una memoria pequeña usando solo tantos contenedores como caben en la memoria y aumentando el número de pases correspondientemente, en en cuyo caso, el tiempo de ejecución ya no es O (n) sino que es O (n * log n).

• El método de XOR 'unir todos los números juntos, mencionado hasta ahora por rfrankel y por último por ircmaxell responde a la pregunta formulada en stackoverflow # 35185 , como señaló ltn100. Utiliza el almacenamiento O (1) y el tiempo de ejecución O (n). Si por el momento asumimos enteros de 32 bits, XOR tiene una probabilidad del 7% de producir un número distinto. Justificación: dado ~ 4G números distintos XOR'd juntos, y ca. 300M no en archivo, el número de bits establecidos en cada posición de bit tiene la misma posibilidad de ser par o impar. Por lo tanto, 2 ^ 32 números tienen la misma probabilidad de surgir que el resultado XOR, de los cuales el 93% ya están en el archivo. Tenga en cuenta que si los números en el archivo no son todos distintos, aumenta la probabilidad de éxito del método XOR.

Por alguna razón, tan pronto como leí este problema, pensé en la diagonalización. Estoy asumiendo enteros arbitrariamente grandes.

Lee el primer número. Izquierda con cero bits hasta que tenga 4 mil millones de bits. Si el primer bit (de orden superior) es 0, salida 1; de lo contrario, salida 0. (Realmente no tiene que dejar el pad izquierdo: solo genera un 1 si no hay suficientes bits en el número). Haga lo mismo con el segundo número, excepto que use su segundo bit. Continúe a través del archivo de esta manera. Producirá un número de 4 mil millones de bits un bit a la vez, y ese número no será el mismo que ninguno en el archivo. Prueba: era lo mismo que el enésimo número, luego estarían de acuerdo con el enésimo bit, pero no lo hacen por construcción.

Puede usar banderas de bits para marcar si un entero está presente o no.

Después de recorrer todo el archivo, escanee cada bit para determinar si el número existe o no.

Suponiendo que cada número entero sea de 32 bits, encajarán convenientemente en 1 GB de RAM si se realiza la marcación de bits.

Elimine el espacio en blanco y los caracteres no numéricos del archivo y agregue 1. Su archivo ahora contiene un solo número que no figura en el archivo original.

De Reddit por Carbonetc.

Solo por completar, aquí hay otra solución muy simple, que probablemente tomará mucho tiempo en ejecutarse, pero usa muy poca memoria.

Deje que todos los enteros posibles sean el rango de int_mina int_max, y bool isNotInFile(integer)una función que devuelve verdadero si el archivo no contiene un cierto entero y falso más (comparando ese entero con cada entero en el archivo)

for (integer i = int_min; i <= int_max; ++i)
{
    if (isNotInFile(i)) {
        return i;
    }
}

Para la restricción de memoria de 10 MB:

1. Convierta el número a su representación binaria.
2. Cree un árbol binario donde left = 0 y right = 1.
3. Inserte cada número en el árbol usando su representación binaria.
4. Si ya se ha insertado un número, las hojas ya se habrán creado.

Cuando termine, simplemente tome una ruta que no se haya creado antes para crear el número solicitado.

4.000 millones = 2 ^ 32, lo que significa que 10 MB podrían no ser suficientes.

EDITAR

Es posible una optimización, si se han creado dos hojas finales y tienen un elemento primario común, entonces se pueden eliminar y marcar el elemento primario como no una solución. Esto corta ramas y reduce la necesidad de memoria.

EDITAR II

No hay necesidad de construir el árbol completamente también. Solo necesita construir ramas profundas si los números son similares. Si también cortamos ramas, entonces esta solución podría funcionar de hecho.

Contestaré la versión de 1 GB:

No hay suficiente información en la pregunta, por lo que expondré algunas suposiciones primero:

El entero es de 32 bits con un rango de -2,147,483,648 a 2,147,483,647.

Pseudocó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;
    }
}

Mientras hagamos respuestas creativas, aquí hay otra.

Use el programa de ordenamiento externo para ordenar el archivo de entrada numéricamente. Esto funcionará para cualquier cantidad de memoria que pueda tener (usará el almacenamiento de archivos si es necesario). Lea el archivo ordenado y muestre el primer número que falta.

Eliminación de bits

Una forma es eliminar bits, sin embargo, esto podría no producir un resultado (lo más probable es que no lo haga). Psuedocódigo:

long val = 0xFFFFFFFFFFFFFFFF; // (all bits set)
foreach long fileVal in file
{
    val = val & ~fileVal;
    if (val == 0) error;
}

Bit Counts

Lleve un registro de los recuentos de bits; y use los bits con la menor cantidad para generar un valor. Nuevamente, esto no tiene garantía de generar un valor correcto.

Lógica de rango

Mantenga un registro de una lista de rangos ordenados (ordenados por inicio). Un rango está definido por la estructura:

struct Range
{
  long Start, End; // Inclusive.
}
Range startRange = new Range { Start = 0x0, End = 0xFFFFFFFFFFFFFFFF };

Revise cada valor en el archivo e intente eliminarlo del rango actual. Este método no tiene garantías de memoria, pero debería funcionar bastante bien.

2 ^{128 * 10 18} + 1 (que es (2 ⁸ ) ^{16 * 10 18} + 1) - ¿no puede ser una respuesta universal para hoy? Esto representa un número que no se puede guardar en un archivo 16 EB, que es el tamaño máximo de archivo en cualquier sistema de archivos actual.

Creo que este es un problema resuelto (ver arriba), pero hay un caso secundario interesante a tener en cuenta porque podría preguntarse:

Si hay exactamente 4,294,967,295 (2 ^ 32 - 1) enteros de 32 bits sin repeticiones y, por lo tanto, solo falta uno, hay una solución simple.

Comience un total acumulado en cero, y para cada número entero en el archivo, agregue ese número entero con un desbordamiento de 32 bits (efectivamente, runningTotal = (runningTotal + nextInteger)% 4294967296). Una vez completado, agregue 4294967296/2 al total acumulado, nuevamente con un desbordamiento de 32 bits. Resta esto de 4294967296, y el resultado es el entero que falta.

El problema de "solo un entero faltante" se puede resolver con una sola ejecución y solo 64 bits de RAM dedicados a los datos (32 para el total acumulado, 32 para leer en el siguiente entero).

Corolario: la especificación más general es extremadamente simple de igualar si no nos preocupa cuántos bits debe tener el resultado entero. Simplemente generamos un número entero lo suficientemente grande como para que no pueda estar contenido en el archivo que se nos proporciona. De nuevo, esto ocupa una RAM absolutamente mínima. Ver el pseudocódigo.

# 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<sz; c++) {
  for (b=0; b<4; b++) {
    print "2";
  }
}

Como Ryan lo dijo básicamente, ordena el archivo y luego revisa los enteros y cuando se omite un valor allí, lo tienes :)

EDITAR en downvoters: el OP mencionó que el archivo podría clasificarse, por lo que este es un método válido.

Si no asume la restricción de 32 bits, simplemente devuelva un número de 64 bits generado aleatoriamente (o 128 bits si es un pesimista). La posibilidad de colisión es 1 in 2^64/(4*10^9) = 4611686018.4(aproximadamente 1 en 4 mil millones). ¡Tendrías razón la mayor parte del tiempo!

(Bromeando ... más o menos)