La pregunta fácil de la entrevista se hizo más difícil: dados los números 1..100, encuentre los números faltantes dados exactamente k faltan

Tuve una interesante experiencia de entrevista de trabajo hace un tiempo. La pregunta comenzó realmente fácil:

Q1 : Tenemos una bolsa que contenía los números 1, 2, 3, ..., 100. Cada número aparece exactamente una vez, por lo que hay 100 números. Ahora se saca un número al azar de la bolsa. Encuentre el número perdido.

He escuchado esta pregunta de la entrevista antes, por supuesto, así que rápidamente respondí en la línea de:

A1 : Bueno, la suma de los números 1 + 2 + 3 + … + Nes (N+1)(N/2)(ver Wikipedia: suma de series aritméticas ). Para N = 100, la suma es 5050.

Por lo tanto, si todos los números están presentes en la bolsa, la suma será exactamente 5050. Como falta un número, la suma será menor que esto, y la diferencia es ese número. Entonces podemos encontrar ese número faltante en el O(N)tiempo y el O(1)espacio.

En este punto, pensé que lo había hecho bien, pero de repente la pregunta tomó un giro inesperado:

P2 : Eso es correcto, pero ahora, ¿cómo haría esto si faltan DOS números?

Nunca antes había visto / escuchado / considerado esta variación, así que entré en pánico y no pude responder la pregunta. El entrevistador insistió en conocer mi proceso de pensamiento, por lo que mencioné que quizás podamos obtener más información comparándolo con el producto esperado, o tal vez haciendo un segundo pase después de haber reunido alguna información del primer pase, etc., pero realmente solo estaba disparando en la oscuridad en lugar de tener un camino claro hacia la solución.

El entrevistador intentó alentarme diciendo que tener una segunda ecuación es, de hecho, una forma de resolver el problema. En este punto, estaba un poco molesto (por no saber la respuesta de antemano), y le pregunté si esta es una técnica de programación general (léase: "útil"), o si es solo una respuesta truco / gotcha.

La respuesta del entrevistador me sorprendió: puedes generalizar la técnica para encontrar 3 números faltantes. De hecho, puede generalizarlo para encontrar k números faltantes.

Qk : Si faltan exactamente k números de la bolsa, ¿cómo lo encontrarían eficientemente?

Esto fue hace unos meses, y todavía no podía entender qué es esta técnica. Obviamente hay un Ω(N)tiempo límite inferior ya que debemos analizar todos los números al menos una vez, pero el entrevistador insistido en que el TIEMPO y ESPACIO complejidad de la técnica de la solución (menos la O(N)exploración de entradas de tiempo) se define en k no N .

Entonces la pregunta aquí es simple:

• ¿Cómo resolverías la Q2 ?
• ¿Cómo resolverías la Q3 ?
• ¿Cómo resolverías Qk ?

Aclaraciones

• Generalmente hay N números de 1 .. N , no solo 1..100.
• No estoy buscando la solución obvia basada en conjuntos, por ejemplo, utilizando un conjunto de bits , codificando la presencia / ausencia de cada número por el valor de un bit designado, por lo tanto, utilizando O(N)bits en espacio adicional. No nos podemos permitir ningún espacio adicional proporcional a N .
• Tampoco estoy buscando el enfoque obvio de ordenar primero. Vale la pena mencionar este y el enfoque basado en conjuntos en una entrevista (son fáciles de implementar y, dependiendo de N , pueden ser muy prácticos). Estoy buscando la solución del Santo Grial (que puede o no ser práctica de implementar, pero sin embargo tiene las características asintóticas deseadas).

De nuevo, por supuesto, debe escanear la entrada O(N), pero solo puede capturar una pequeña cantidad de información (definida en términos de k no N ), y luego debe encontrar los k números que faltan de alguna manera.

Aquí hay un resumen del enlace de Dimitris Andreou .

Recuerde la suma de las i-ésimas potencias, donde i = 1,2, .., k. Esto reduce el problema de resolver el sistema de ecuaciones.

a ₁ + a ₂ + ... + a _k = b ₁

a ₁ ² + a ₂ ² + ... + a _k ² = b ₂

...

a ₁ ^k + a ₂ ^k + ... + a _k ^k = b _k

Usando las identidades de Newton , saber b _i permite calcular

c ₁ = a ₁ + a ₂ + ... a _k

c ₂ = a ₁ a ₂ + a ₁ a ₃ + ... + a _k-1 a _k

...

c _k = a ₁ a ₂ ... a _k

Si expande el polinomio (xa ₁ ) ... (xa _k ) los coeficientes serán exactamente c ₁ , ..., c _k - vea las fórmulas de Viète . Dado que cada factor polinómico es único (el anillo de polinomios es un dominio euclidiano ), esto significa que _i está determinado de manera única, hasta la permutación.

Esto termina con una prueba de que recordar poderes es suficiente para recuperar los números. Para k constante, este es un buen enfoque.

Sin embargo, cuando k varía, el enfoque directo de la computación c ₁ , ..., c _k es prohibitivamente costoso, ya que, por ejemplo, c _k es el producto de todos los números faltantes, ¡magnitud n! / (Nk) !. Para superar esto, realice cálculos en el campo Z _q , donde q es primo tal que n <= q <2n, existe por el postulado de Bertrand . No es necesario cambiar la prueba, ya que las fórmulas aún se mantienen y la factorización de polinomios sigue siendo única. También necesita un algoritmo para la factorización sobre campos finitos, por ejemplo, el de Berlekamp o Cantor-Zassenhaus .

Pseudocódigo de alto nivel para k constante:

• Calcular i-ésima potencia de números dados
• Resta para obtener sumas de i-ésima potencia de números desconocidos. Llame las sumas b _i .
• Utilice las identidades de Newton para calcular los coeficientes de b _i ; llámalos c _i . Básicamente, c ₁ = b ₁ ; c ₂ = (c ₁ b ₁ - b ₂ ) / 2; ver Wikipedia para fórmulas exactas
• Factoriza el polinomio x ^k -c ₁ x ^k-1 + ... + c _k .
• Las raíces del polinomio son los números necesarios a ₁ , ..., a _k .

Para variar k, encuentre un primo n <= q <2n usando, por ejemplo, Miller-Rabin, y realice los pasos con todos los números de módulo reducido q.

EDITAR: La versión anterior de esta respuesta indicaba que en lugar de Z _q , donde q es primo, es posible usar un campo finito de la característica 2 (q = 2 ^ (log n)). Este no es el caso, ya que las fórmulas de Newton requieren división por números hasta k.

Lo encontrará leyendo las dos páginas de Muthukrishnan - Algoritmos de flujo de datos: Rompecabezas 1: Encontrar números que faltan . Muestra exactamente la generalización que está buscando . Probablemente esto es lo que leyó su entrevistador y por qué planteó estas preguntas.

Ahora, si solo las personas comenzaran a eliminar las respuestas que están incluidas o reemplazadas por el tratamiento de Muthukrishnan, y hacer que este texto sea más fácil de encontrar. :)

También vea la respuesta directamente relacionada de sdcvvc , que también incluye pseudocódigo (¡hurra! No es necesario leer esas complicadas formulaciones matemáticas :)) (¡gracias, gran trabajo!).

Podemos resolver Q2 sumando tanto los números como los cuadrados de los números.

Entonces podemos reducir el problema a

k1 + k2 = x
k1^2 + k2^2 = y

Dónde xy yqué tan lejos están las sumas por debajo de los valores esperados.

Sustituir nos da:

(x-k2)^2 + k2^2 = y

Lo que luego podemos resolver para determinar nuestros números faltantes.

Como señaló @j_random_hacker, esto es bastante similar a Encontrar duplicados en O (n) tiempo y O (1) espacio , y una adaptación de mi respuesta allí también funciona aquí.

Suponiendo que la "bolsa" está representada por una matriz A[]de tamaño basada en 1 N - k, podemos resolver Qk en O(N)tiempo y O(k)espacio adicional.

Primero, extendemos nuestra matriz A[]por kelementos, de modo que ahora sea de tamaño N. Este es el O(k)espacio adicional. Luego ejecutamos el siguiente algoritmo de pseudocódigo:

for i := n - k + 1 to n
    A[i] := A[1]
end for

for i := 1 to n - k
    while A[A[i]] != A[i] 
        swap(A[i], A[A[i]])
    end while
end for

for i := 1 to n
    if A[i] != i then 
        print i
    end if
end for

El primer bucle inicializa las kentradas adicionales de la misma manera que la primera entrada en la matriz (este es solo un valor conveniente que sabemos que ya está presente en la matriz; después de este paso, las entradas que faltaban en la matriz inicial de tamaño N-kson todavía falta en la matriz extendida).

El segundo bucle permuta la matriz extendida de modo que si el elemento xestá presente al menos una vez, una de esas entradas estará en la posición A[x].

Tenga en cuenta que aunque tiene un bucle anidado, todavía se ejecuta a O(N)tiempo: un intercambio solo ocurre si existe ital cosa A[i] != i, y cada intercambio establece al menos un elemento tal que A[i] == i, donde eso no era cierto antes. Esto significa que el número total de intercambios (y, por lo tanto, el número total de ejecuciones del whilecuerpo del bucle) es como máximo N-1.

El tercer bucle imprime los índices de la matriz ique no están ocupados por el valor i, lo que significa que ideben haberse perdido.

Le pedí a un niño de 4 años que resolviera este problema. Ordenó los números y luego contó. Esto tiene un requerimiento de espacio de O (piso de la cocina), y funciona igual de fácil, sin embargo, faltan muchas bolas.

No estoy seguro, si es la solución más eficiente, pero haría un bucle sobre todas las entradas y usaría un conjunto de bits para recordar qué números están configurados y luego probaría para 0 bits.

Me gustan las soluciones simples, e incluso creo que podría ser más rápido que calcular la suma, la suma de cuadrados, etc.

No he revisado las matemáticas, pero sospecho que computar Σ(n^2)en el mismo paso que calculamos Σ(n)proporcionaría suficiente información para obtener dos números faltantes, haz Σ(n^3)lo mismo si hay tres, y así sucesivamente.

El problema con las soluciones basadas en sumas de números es que no tienen en cuenta el costo de almacenar y trabajar con números con grandes exponentes ... en la práctica, para que funcione para n muy grande, se usaría una biblioteca de grandes números . Podemos analizar la utilización del espacio para estos algoritmos.

Podemos analizar la complejidad de tiempo y espacio de los algoritmos de sdcvvc y Dimitris Andreou.

Almacenamiento:

l_j = ceil (log_2 (sum_{i=1}^n i^j))
l_j > log_2 n^j  (assuming n >= 0, k >= 0)
l_j > j log_2 n \in \Omega(j log n)

l_j < log_2 ((sum_{i=1}^n i)^j) + 1
l_j < j log_2 (n) + j log_2 (n + 1) - j log_2 (2) + 1
l_j < j log_2 n + j + c \in O(j log n)`

Entonces l_j \in \Theta(j log n)

Almacenamiento total utilizado: \sum_{j=1}^k l_j \in \Theta(k^2 log n)

Espacio utilizado: suponiendo que la informática a^jlleva ceil(log_2 j)tiempo, tiempo total:

t = k ceil(\sum_i=1^n log_2 (i)) = k ceil(log_2 (\prod_i=1^n (i)))
t > k log_2 (n^n + O(n^(n-1)))
t > k log_2 (n^n) = kn log_2 (n)  \in \Omega(kn log n)
t < k log_2 (\prod_i=1^n i^i) + 1
t < kn log_2 (n) + 1 \in O(kn log n)

Tiempo total utilizado: \Theta(kn log n)

Si este tiempo y espacio son satisfactorios, puede usar un algoritmo recursivo simple. Sea b! I la entrada i-ésima en la bolsa, n el número de números antes de los retiros, yk el número de retiros. En la sintaxis de Haskell ...

let
  -- O(1)
  isInRange low high v = (v >= low) && (v <= high)
  -- O(n - k)
  countInRange low high = sum $ map (fromEnum . isInRange low high . (!)b) [1..(n-k)]
  findMissing l low high krange
    -- O(1) if there is nothing to find.
    | krange=0 = l
    -- O(1) if there is only one possibility.
    | low=high = low:l
    -- Otherwise total of O(knlog(n)) time
    | otherwise =
       let
         mid = (low + high) `div` 2
         klow = countInRange low mid
         khigh = krange - klow
       in
         findMissing (findMissing low mid klow) (mid + 1) high khigh
in
  findMising 1 (n - k) k

Almacenamiento utilizado: O(k)para lista, O(log(n))para pila: O(k + log(n)) este algoritmo es más intuitivo, tiene la misma complejidad de tiempo y usa menos espacio.

Espera un minuto. Como se plantea la pregunta, hay 100 números en la bolsa. No importa cuán grande sea k, el problema puede resolverse en tiempo constante porque puede usar un conjunto y eliminar números del conjunto en un máximo de 100 k iteraciones de un bucle. 100 es constante. El conjunto de números restantes es su respuesta.

Si generalizamos la solución a los números del 1 al N, nada cambia excepto que N no es una constante, por lo que estamos en el tiempo O (N - k) = O (N). Por ejemplo, si usamos un conjunto de bits, establecemos los bits a 1 en tiempo O (N), iteramos a través de los números, configuramos los bits a 0 a medida que avanzamos (O (Nk) = O (N)) y luego tener la respuesta

Me parece que el entrevistador le estaba preguntando cómo imprimir el contenido del conjunto final en tiempo O (k) en lugar de tiempo O (N). Claramente, con un conjunto de bits, debe iterar a través de todos los N bits para determinar si debe imprimir el número o no. Sin embargo, si cambia la forma en que se implementa el conjunto, puede imprimir los números en k iteraciones. Esto se hace colocando los números en un objeto que se almacenará tanto en un conjunto de hash como en una lista doblemente vinculada. Cuando elimina un objeto del conjunto de hash, también lo elimina de la lista. Las respuestas se dejarán en la lista que ahora tiene una longitud k.

Para resolver la pregunta de 2 (y 3) números faltantes, puede modificar quickselect, que en promedio se ejecuta O(n)y usa memoria constante si la partición se realiza en el lugar.

1. Particione el conjunto con respecto a un pivote aleatorio pen particiones l, que contienen números más pequeños que el pivote, y rque contienen números mayores que el pivote.

2. Determine en qué particiones están los 2 números faltantes comparando el valor de pivote con el tamaño de cada partición ( p - 1 - count(l) = count of missing numbers in ly n - count(r) - p = count of missing numbers in r)

3. a) Si a cada partición le falta un número, utilice el enfoque de la diferencia de sumas para encontrar cada número faltante.

   (1 + 2 + ... + (p-1)) - sum(l) = missing #1 y ((p+1) + (p+2) ... + n) - sum(r) = missing #2

   b) Si a una partición le faltan ambos números y la partición está vacía, entonces los números que faltan son (p-1,p-2)o (p+1,p+2) dependen de qué partición faltan los números.

   Si a una partición le faltan 2 números pero no está vacía, vuelva a esa partición.

Con solo 2 números faltantes, este algoritmo siempre descarta al menos una partición, por lo que conserva la O(n)complejidad de tiempo promedio de la selección rápida. De manera similar, con 3 números faltantes, este algoritmo también descarta al menos una partición con cada pasada (porque como con 2 números faltantes, como máximo solo 1 partición contendrá múltiples números faltantes). Sin embargo, no estoy seguro de cuánto disminuye el rendimiento cuando se agregan más números faltantes.

Aquí hay una implementación que no usa particionamiento en el lugar, por lo que este ejemplo no cumple con los requisitos de espacio, pero ilustra los pasos del algoritmo:

<?php

  $list = range(1,100);
  unset($list[3]);
  unset($list[31]);

  findMissing($list,1,100);

  function findMissing($list, $min, $max) {
    if(empty($list)) {
      print_r(range($min, $max));
      return;
    }

    $l = $r = [];
    $pivot = array_pop($list);

    foreach($list as $number) {
      if($number < $pivot) {
        $l[] = $number;
      }
      else {
        $r[] = $number;
      }
    }

    if(count($l) == $pivot - $min - 1) {
      // only 1 missing number use difference of sums
      print array_sum(range($min, $pivot-1)) - array_sum($l) . "\n";
    }
    else if(count($l) < $pivot - $min) {
      // more than 1 missing number, recurse
      findMissing($l, $min, $pivot-1);
    }

    if(count($r) == $max - $pivot - 1) {
      // only 1 missing number use difference of sums
      print array_sum(range($pivot + 1, $max)) - array_sum($r) . "\n";
    } else if(count($r) < $max - $pivot) {
      // mroe than 1 missing number recurse
      findMissing($r, $pivot+1, $max);
    }
  }

Manifestación

Aquí hay una solución que utiliza k bits de almacenamiento adicional, sin ningún truco inteligente y sencillo. Tiempo de ejecución O (n), espacio extra O (k). Solo para demostrar que esto se puede resolver sin leer primero la solución o ser un genio:

void puzzle (int* data, int n, bool* extra, int k)
{
    // data contains n distinct numbers from 1 to n + k, extra provides
    // space for k extra bits. 

    // Rearrange the array so there are (even) even numbers at the start
    // and (odd) odd numbers at the end.
    int even = 0, odd = 0;
    while (even + odd < n)
    {
        if (data [even] % 2 == 0) ++even;
        else if (data [n - 1 - odd] % 2 == 1) ++odd;
        else { int tmp = data [even]; data [even] = data [n - 1 - odd]; 
               data [n - 1 - odd] = tmp; ++even; ++odd; }
    }

    // Erase the lowest bits of all numbers and set the extra bits to 0.
    for (int i = even; i < n; ++i) data [i] -= 1;
    for (int i = 0; i < k; ++i) extra [i] = false;

    // Set a bit for every number that is present
    for (int i = 0; i < n; ++i)
    {
        int tmp = data [i];
        tmp -= (tmp % 2);
        if (i >= even) ++tmp;
        if (tmp <= n) data [tmp - 1] += 1; else extra [tmp - n - 1] = true;
    }

    // Print out the missing ones
    for (int i = 1; i <= n; ++i)
        if (data [i - 1] % 2 == 0) printf ("Number %d is missing\n", i);
    for (int i = n + 1; i <= n + k; ++i)
        if (! extra [i - n - 1]) printf ("Number %d is missing\n", i);

    // Restore the lowest bits again.
    for (int i = 0; i < n; ++i) {
        if (i < even) { if (data [i] % 2 != 0) data [i] -= 1; }
        else { if (data [i] % 2 == 0) data [i] += 1; }
    }
}

¿Puedes verificar si cada número existe? En caso afirmativo, puede intentar esto:

S = suma de todos los números en la bolsa (S <5050)
Z = suma de los números que faltan 5050 - S

si los números que faltan son xy yluego:

x = Z - y y
max (x) = Z - 1

Entonces verifica el rango de 1a max(x)y encuentra el número

Puede ser que este algoritmo funcione para la pregunta 1:

1. Precomputar xor de los primeros 100 enteros (val = 1 ^ 2 ^ 3 ^ 4 .... 100)
2. xor los elementos a medida que siguen viniendo de la secuencia de entrada (val1 = val1 ^ next_input)
3. respuesta final = val ^ val1

O mejor:

def GetValue(A)
  val=0
  for i=1 to 100
    do
      val=val^i
    done
  for value in A:
    do
      val=val^value 
    done
  return val

De hecho, este algoritmo puede expandirse para dos números faltantes. El primer paso sigue siendo el mismo. Cuando llamamos a GetValue con dos números faltantes, el resultado será a a1^a2son los dos números faltantes. Digamos

val = a1^a2

Ahora para tamizar a1 y a2 de val tomamos cualquier bit establecido en val. Digamos que el ithbit se establece en val. Eso significa que a1 y a2 tienen paridad diferente en la ithposición de bit. Ahora hacemos otra iteración en la matriz original y mantenemos dos valores xor. Uno para los números que tienen el conjunto de bits i-ésimo y otro que no tiene el conjunto de bits i-ésimo. Ahora tenemos dos cubos de números, y está garantizado que a1 and a2estarán en cubos diferentes. Ahora repita lo mismo que hicimos para encontrar un elemento faltante en cada uno de los cubos.

Puede resolver Q2 si tiene la suma de ambas listas y el producto de ambas listas.

(l1 es el original, l2 es la lista modificada)

d = sum(l1) - sum(l2)
m = mul(l1) / mul(l2)

Podemos optimizar esto ya que la suma de una serie aritmética es n veces el promedio del primer y último término:

n = len(l1)
d = (n/2)*(n+1) - sum(l2)

Ahora sabemos que (si a y b son los números eliminados):

a + b = d
a * b = m

Entonces podemos reorganizar a:

a = s - b
b * (s - b) = m

Y multiplicar:

-b^2 + s*b = m

Y reorganizar para que el lado derecho sea cero:

-b^2 + s*b - m = 0

Entonces podemos resolver con la fórmula cuadrática:

b = (-s + sqrt(s^2 - (4*-1*-m)))/-2
a = s - b

Código de muestra de Python 3:

from functools import reduce
import operator
import math
x = list(range(1,21))
sx = (len(x)/2)*(len(x)+1)
x.remove(15)
x.remove(5)
mul = lambda l: reduce(operator.mul,l)
s = sx - sum(x)
m = mul(range(1,21)) / mul(x)
b = (-s + math.sqrt(s**2 - (-4*(-m))))/-2
a = s - b
print(a,b) #15,5

No conozco la complejidad de las funciones sqrt, reduce y sum, por lo que no puedo resolver la complejidad de esta solución (si alguien lo sabe, comente a continuación).

Para Q2, esta es una solución que es un poco más ineficiente que las otras, pero que todavía tiene tiempo de ejecución O (N) y ocupa espacio O (k).

La idea es ejecutar el algoritmo original dos veces. En el primero obtienes un número total que falta, que te da un límite superior de los números que faltan. Llamemos a este número N. Usted sabe que los dos números que faltan van a sumar N, por lo que el primer número solo puede estar en el intervalo [1, floor((N-1)/2)]mientras que el segundo va a estar dentro [floor(N/2)+1,N-1].

Por lo tanto, realiza un bucle en todos los números una vez más, descartando todos los números que no están incluidos en el primer intervalo. Los que son, lleva un registro de su suma. Finalmente, conocerá uno de los dos números que faltan y, por extensión, el segundo.

Tengo la sensación de que este método podría generalizarse y tal vez se ejecuten múltiples búsquedas en "paralelo" durante una sola pasada sobre la entrada, pero aún no he descubierto cómo.

Creo que esto se puede hacer sin ecuaciones y teorías matemáticas complejas. A continuación se muestra una propuesta para una solución de complejidad de tiempo in situ y O (2n):

Supuestos del formulario de entrada:

# de números en la bolsa = n

# de números faltantes = k

Los números en la bolsa están representados por una matriz de longitud n

Longitud de la matriz de entrada para algo = n

Las entradas que faltan en la matriz (números extraídos de la bolsa) se reemplazan por el valor del primer elemento de la matriz.

P.ej. Inicialmente, la bolsa se ve como [2,9,3,7,8,6,4,5,1,10]. Si se saca 4, el valor de 4 se convertirá en 2 (el primer elemento de la matriz). Por lo tanto, después de sacar 4, la bolsa se verá como [2,9,3,7,8,6,2,5,1,10]

La clave de esta solución es etiquetar el ÍNDICE de un número visitado negando el valor en ese ÍNDICE a medida que se recorre la matriz.

    IEnumerable<int> GetMissingNumbers(int[] arrayOfNumbers)
    {
        List<int> missingNumbers = new List<int>();
        int arrayLength = arrayOfNumbers.Length;

        //First Pass
        for (int i = 0; i < arrayLength; i++)
        {
            int index = Math.Abs(arrayOfNumbers[i]) - 1;
            if (index > -1)
            {
                arrayOfNumbers[index] = Math.Abs(arrayOfNumbers[index]) * -1; //Marking the visited indexes
            }
        }

        //Second Pass to get missing numbers
        for (int i = 0; i < arrayLength; i++)
        {                
            //If this index is unvisited, means this is a missing number
            if (arrayOfNumbers[i] > 0)
            {
                missingNumbers.Add(i + 1);
            }
        }

        return missingNumbers;
    }

Hay una forma general de generalizar algoritmos de transmisión como este. La idea es utilizar un poco de aleatorización para, con suerte, 'difundir' los kelementos en subproblemas independientes, donde nuestro algoritmo original nos resuelve el problema. Esta técnica se utiliza en la reconstrucción de señales dispersas, entre otras cosas.

• Haga una matriz a, de tamaño u = k^2.
• Escoja cualquier función hash universales , h : {1,...,n} -> {1,...,u}. (Al igual que el turno múltiple )
• Para cada uno ien 1, ..., naumentoa[h(i)] += i
• Para cada número xen la secuencia de entrada, decremente a[h(x)] -= x.

Si todos los números faltantes se han dividido en segmentos diferentes, los elementos distintos de cero de la matriz ahora contendrán los números faltantes.

La probabilidad de que un par particular se envíe al mismo depósito es menor que 1/upor definición de una función hash universal. Como hay aproximadamente k^2/2pares, tenemos que la probabilidad de error es como máximo k^2/2/u=1/2. Es decir, tenemos éxito con una probabilidad de al menos 50%, y si uaumentamos aumentamos nuestras posibilidades.

Tenga en cuenta que este algoritmo ocupa k^2 lognbits de espacio (necesitamos lognbits por segmento de matriz). Esto coincide con el espacio requerido por la respuesta de @Dimitris Andreou (en particular, el requisito de espacio de factorización polinómica, que también es aleatorio). Este algoritmo también tiene constante tiempo por actualización, en lugar de tiempo ken el caso de sumas de potencia.

De hecho, podemos ser aún más eficientes que el método de la suma de potencia utilizando el truco descrito en los comentarios.

Una solución muy simple para Q2 que me sorprende que nadie haya respondido ya. Usa el método de Q1 para encontrar la suma de los dos números que faltan. Denotémoslo por S, entonces uno de los números que faltan es menor que S / 2 y el otro es mayor que S / 2 (duh). Suma todos los números del 1 al S / 2 y compáralo con el resultado de la fórmula (de manera similar al método en Q1) para encontrar el menor entre los números que faltan. Restarlo de S para encontrar el número que falta más grande.

Muy buen problema. Me gustaría usar una diferencia establecida para Qk. Muchos lenguajes de programación incluso lo admiten, como en Ruby:

missing = (1..100).to_a - bag

Probablemente no sea la solución más eficiente, pero es una que usaría en la vida real si me enfrentara a tal tarea en este caso (límites conocidos, límites bajos). Si el conjunto de números fuera muy grande, consideraría un algoritmo más eficiente, por supuesto, pero hasta entonces la solución simple sería suficiente para mí.

Puedes intentar usar un filtro Bloom . Inserta cada número en la bolsa en la flor, luego itera sobre el conjunto completo de 1-k hasta informar cada uno que no se encuentre. Es posible que esto no encuentre la respuesta en todos los escenarios, pero podría ser una solución lo suficientemente buena.

Tomaría un enfoque diferente a esa pregunta e investigaría al entrevistador para obtener más detalles sobre el gran problema que está tratando de resolver. Dependiendo del problema y los requisitos que lo rodean, la solución obvia basada en conjuntos podría ser lo correcto y el enfoque de generar una lista y elegirlo después podría no serlo.

Por ejemplo, puede ser que el entrevistador envíe nmensajes y necesite saber kque eso no resultó en una respuesta y necesita saberlo en el menor tiempo posible del reloj de pared después de que n-kllegue la respuesta. Supongamos también que la naturaleza del canal de mensajes es tal que incluso cuando se ejecuta a toda potencia, hay suficiente tiempo para procesar algo entre mensajes sin tener ningún impacto en cuánto tiempo se tarda en producir el resultado final después de que llega la última respuesta. Se puede aprovechar ese tiempo insertando una faceta de identificación de cada mensaje enviado en un conjunto y eliminándolo a medida que llegue cada respuesta correspondiente. Una vez que llega la última respuesta, lo único que se debe hacer es eliminar su identificador del conjunto, que en implementaciones típicas tomaO(log k+1). Después de eso, el conjunto contiene la lista de kelementos que faltan y no hay procesamiento adicional para hacer.

Ciertamente, este no es el enfoque más rápido para el procesamiento por lotes de bolsas pregeneradas de números porque todo funciona O((log 1 + log 2 + ... + log n) + (log n + log n-1 + ... + log k)). Pero funciona para cualquier valor de k(incluso si no se conoce con anticipación) y en el ejemplo anterior se aplicó de una manera que minimiza el intervalo más crítico.

Puede motivar la solución al pensar en términos de simetrías (grupos, en lenguaje matemático). No importa el orden del conjunto de números, la respuesta debe ser la misma. Si va a utilizar kfunciones para ayudar a determinar los elementos que faltan, debe pensar qué funciones tienen esa propiedad: simétrica. La función s_1(x) = x_1 + x_2 + ... + x_nes un ejemplo de una función simétrica, pero hay otras de mayor grado. En particular, considere las funciones simétricas elementales . La función simétrica elemental del grado 2 es s_2(x) = x_1 x_2 + x_1 x_3 + ... + x_1 x_n + x_2 x_3 + ... + x_(n-1) x_nla suma de todos los productos de dos elementos. Del mismo modo para las funciones simétricas elementales de grado 3 y superior. Obviamente son simétricos. Además, resulta que son los bloques de construcción para todas las funciones simétricas.

Puede construir las funciones simétricas elementales a medida que avanza al notar eso s_2(x,x_(n+1)) = s_2(x) + s_1(x)(x_(n+1)). Pensar más sobre esto debería convencerlo de que s_3(x,x_(n+1)) = s_3(x) + s_2(x)(x_(n+1))así sucesivamente, para que puedan calcularse de una sola vez.

¿Cómo sabemos qué elementos faltaban en la matriz? Piensa en el polinomio (z-x_1)(z-x_2)...(z-x_n). Se evalúa 0si pones alguno de los números x_i. Expandiendo el polinomio, obtienes z^n-s_1(x)z^(n-1)+ ... + (-1)^n s_n. Aquí también aparecen las funciones simétricas elementales, lo cual no es una sorpresa, ya que el polinomio debería permanecer igual si aplicamos alguna permutación a las raíces.

Entonces podemos construir el polinomio e intentar factorizarlo para descubrir qué números no están en el conjunto, como otros han mencionado.

Finalmente, si estamos preocupados por el desbordamiento de memoria con números grandes (el enésimo polinomio simétrico será del orden 100!), podemos hacer estos cálculos mod pdonde pes un primo mayor que 100. En ese caso, evaluamos el polinomio mod py descubrimos que nuevamente evalúa a 0cuando la entrada es un número en el conjunto, y se evalúa a un valor distinto de cero cuando la entrada es un número que no está en el conjunto. Sin embargo, como otros han señalado, para obtener los valores del polinomio en el tiempo que depende k, no N, tenemos que factorizar el polinomio mod p.

Sin embargo, otra forma es usar el filtrado gráfico residual.

Supongamos que tenemos los números 1 a 4 y falta 3. La representación binaria es la siguiente,

1 = 001b, 2 = 010b, 3 = 011b, 4 = 100b

Y puedo crear un diagrama de flujo como el siguiente.

                   1
             1 -------------> 1
             |                | 
      2      |     1          |
0 ---------> 1 ----------> 0  |
|                          |  |
|     1            1       |  |
0 ---------> 0 ----------> 0  |
             |                |
      1      |      1         |
1 ---------> 0 -------------> 1

Tenga en cuenta que el gráfico de flujo contiene x nodos, mientras que x es el número de bits. Y el número máximo de aristas es (2 * x) -2.

Entonces, para un entero de 32 bits, ocupará O (32) espacio u O (1) espacio.

Ahora, si elimino la capacidad de cada número a partir de 1,2,4, me queda un gráfico residual.

0 ----------> 1 ---------> 1

Finalmente ejecutaré un bucle como el siguiente,

 result = []
 for x in range(1,n):
     exists_path_in_residual_graph(x)
     result.append(x)

Ahora el resultado está en resultcontiene números que no faltan también (falso positivo). Pero la k <= (tamaño del resultado) <= n cuando kfaltan elementos.

Revisaré la lista dada por última vez para marcar el resultado como perdido o no.

Entonces la complejidad del tiempo será O (n).

Finalmente, es posible reducir el número de falsos positivos (y el espacio necesario) mediante la adopción de nodos 00, 01, 11, 10en lugar de sólo 0y 1.

Probablemente necesite aclaraciones sobre lo que significa O (k).

Aquí hay una solución trivial para k arbitraria: para cada v en su conjunto de números, acumule la suma de 2 ^ v. Al final, repita i de 1 a N. Si la suma AND con 2 bits i es cero, entonces me falta. (O numéricamente, si el piso de la suma dividido por 2 ^ i es par. Or sum modulo 2^(i+1)) < 2^i.)

Fácil, verdad? O (N) tiempo, O (1) almacenamiento, y admite k arbitrario.

Excepto que estás calculando números enormes que en una computadora real requerirían espacio O (N). De hecho, esta solución es idéntica a un vector de bits.

Entonces podría ser inteligente y calcular la suma y la suma de los cuadrados y la suma de los cubos ... hasta la suma de v ^ k, y hacer las matemáticas elegantes para extraer el resultado. Pero esos también son números grandes, lo que plantea la pregunta: ¿de qué modelo abstracto de operación estamos hablando? ¿Cuánto cabe en el espacio O (1) y cuánto tiempo lleva sumar números del tamaño que necesite?

Aquí hay una solución que no se basa en matemáticas complejas como lo hacen las respuestas de sdcvvc / Dimitris Andreou, no cambia la matriz de entrada como lo hicieron caf y Coronel Panic, y no usa el bitset de enorme tamaño como Chris Lercher, JeremyP y muchos otros lo hicieron. Básicamente, comencé con la idea de Svalorzen / Gilad Deutch para Q2, la generalicé al caso común Qk y la implementé en Java para demostrar que el algoritmo funciona.

La idea

Supongamos que tenemos un intervalo arbitrario I del cual solo sabemos que contiene al menos uno de los números que faltan. Después de una pasada a través de la matriz de entrada, mirando sólo los números de I , podemos obtener tanto la suma S y la cantidad Q de los números que falta de I . Hacemos esto simplemente disminuyendo la longitud de I cada vez que encontramos un número de I (para obtener Q ) y disminuyendo la suma calculada previamente de todos los números en I por ese número encontrado cada vez (para obtener S ).

Ahora nos centraremos en S y Q . Si Q = 1 , significa que entonces me contiene sólo uno de los números que faltan, y este número es claramente S . Marcamos I como terminado (se llama "inequívoco" en el programa) y lo dejamos fuera de consideración. Por otro lado, si Q> 1 , se puede calcular el promedio A = S / Q de los números que faltan contenida en I . Como todos los números son distintos, al menos uno de dichos números es estrictamente menor que A y al menos una es estrictamente mayor que A . Ahora nos separamos yo en unaen dos intervalos más pequeños, cada uno de los cuales contiene al menos un número faltante. Tenga en cuenta que no importa a cuál de los intervalos asignamos A en caso de que sea un número entero.

Realizamos el siguiente paso de matriz calculando S y Q para cada uno de los intervalos por separado (pero en el mismo paso) y luego marcamos los intervalos con Q = 1 y los intervalos divididos con Q> 1 . Continuamos este proceso hasta que no haya nuevos intervalos "ambiguos", es decir, no tenemos nada que dividir porque cada intervalo contiene exactamente un número faltante (y siempre sabemos este número porque sabemos S ). Comenzamos desde el único intervalo de "rango completo" que contiene todos los números posibles (como [1..N] en la pregunta).

Análisis de complejidad de tiempo y espacio.

El número total de pases p que necesitamos hacer hasta que el proceso se detenga nunca es mayor que los números faltantes cuentan k . La desigualdad p <= k puede demostrarse rigurosamente. Por otro lado, también hay un límite superior empírico p <log ₂ N + 3 que es útil para valores grandes de k . Necesitamos hacer una búsqueda binaria para cada número de la matriz de entrada para determinar el intervalo al que pertenece. Esto agrega el multiplicador log k a la complejidad del tiempo.

En total, la complejidad del tiempo es O (N ᛫ min (k, log N) ᛫ log k) . Tenga en cuenta que para k grande , esto es significativamente mejor que el del método sdcvvc / Dimitris Andreou, que es O (N ᛫ k) .

Para su trabajo, el algoritmo requiere O (k) de espacio adicional para almacenar en la mayoría de los intervalos de k , que es significativamente mejor que O (N) en soluciones de "conjunto de bits".

Implementación de Java

Aquí hay una clase de Java que implementa el algoritmo anterior. Siempre devuelve una matriz ordenada de números faltantes. Además de eso, no requiere que los números que faltan cuenten k porque lo calcula en la primera pasada. El rango completo de números viene dado por los parámetros minNumbery maxNumber(por ejemplo, 1 y 100 para el primer ejemplo en la pregunta).

public class MissingNumbers {
    private static class Interval {
        boolean ambiguous = true;
        final int begin;
        int quantity;
        long sum;

        Interval(int begin, int end) { // begin inclusive, end exclusive
            this.begin = begin;
            quantity = end - begin;
            sum = quantity * ((long)end - 1 + begin) / 2;
        }

        void exclude(int x) {
            quantity--;
            sum -= x;
        }
    }

    public static int[] find(int minNumber, int maxNumber, NumberBag inputBag) {
        Interval full = new Interval(minNumber, ++maxNumber);
        for (inputBag.startOver(); inputBag.hasNext();)
            full.exclude(inputBag.next());
        int missingCount = full.quantity;
        if (missingCount == 0)
            return new int[0];
        Interval[] intervals = new Interval[missingCount];
        intervals[0] = full;
        int[] dividers = new int[missingCount];
        dividers[0] = minNumber;
        int intervalCount = 1;
        while (true) {
            int oldCount = intervalCount;
            for (int i = 0; i < oldCount; i++) {
                Interval itv = intervals[i];
                if (itv.ambiguous)
                    if (itv.quantity == 1) // number inside itv uniquely identified
                        itv.ambiguous = false;
                    else
                        intervalCount++; // itv will be split into two intervals
            }
            if (oldCount == intervalCount)
                break;
            int newIndex = intervalCount - 1;
            int end = maxNumber;
            for (int oldIndex = oldCount - 1; oldIndex >= 0; oldIndex--) {
                // newIndex always >= oldIndex
                Interval itv = intervals[oldIndex];
                int begin = itv.begin;
                if (itv.ambiguous) {
                    // split interval itv
                    // use floorDiv instead of / because input numbers can be negative
                    int mean = (int)Math.floorDiv(itv.sum, itv.quantity) + 1;
                    intervals[newIndex--] = new Interval(mean, end);
                    intervals[newIndex--] = new Interval(begin, mean);
                } else
                    intervals[newIndex--] = itv;
                end = begin;
            }
            for (int i = 0; i < intervalCount; i++)
                dividers[i] = intervals[i].begin;
            for (inputBag.startOver(); inputBag.hasNext();) {
                int x = inputBag.next();
                // find the interval to which x belongs
                int i = java.util.Arrays.binarySearch(dividers, 0, intervalCount, x);
                if (i < 0)
                    i = -i - 2;
                Interval itv = intervals[i];
                if (itv.ambiguous)
                    itv.exclude(x);
            }
        }
        assert intervalCount == missingCount;
        for (int i = 0; i < intervalCount; i++)
            dividers[i] = (int)intervals[i].sum;
        return dividers;
    }
}

Para ser justos, esta clase recibe información en forma de NumberBagobjetos. NumberBagno permite la modificación de la matriz y el acceso aleatorio y también cuenta cuántas veces se solicitó la matriz para el recorrido secuencial. También es más adecuado para pruebas de matriz grande que Iterable<Integer>porque evita el encajonamiento de intvalores primitivos y permite envolver una parte de una gran int[]para una preparación de prueba conveniente. No es difícil de reemplazar, en caso dado, NumberBagpor int[]o Iterable<Integer>escribir en la findfirma, mediante el cambio de dos bucles en que foreach en otros más.

import java.util.*;

public abstract class NumberBag {
    private int passCount;

    public void startOver() {
        passCount++;
    }

    public final int getPassCount() {
        return passCount;
    }

    public abstract boolean hasNext();

    public abstract int next();

    // A lightweight version of Iterable<Integer> to avoid boxing of int
    public static NumberBag fromArray(int[] base, int fromIndex, int toIndex) {
        return new NumberBag() {
            int index = toIndex;

            public void startOver() {
                super.startOver();
                index = fromIndex;
            }

            public boolean hasNext() {
                return index < toIndex;
            }

            public int next() {
                if (index >= toIndex)
                    throw new NoSuchElementException();
                return base[index++];
            }
        };
    }

    public static NumberBag fromArray(int[] base) {
        return fromArray(base, 0, base.length);
    }

    public static NumberBag fromIterable(Iterable<Integer> base) {
        return new NumberBag() {
            Iterator<Integer> it;

            public void startOver() {
                super.startOver();
                it = base.iterator();
            }

            public boolean hasNext() {
                return it.hasNext();
            }

            public int next() {
                return it.next();
            }
        };
    }
}

Pruebas

A continuación se dan ejemplos simples que demuestran el uso de estas clases.

import java.util.*;

public class SimpleTest {
    public static void main(String[] args) {
        int[] input = { 7, 1, 4, 9, 6, 2 };
        NumberBag bag = NumberBag.fromArray(input);
        int[] output = MissingNumbers.find(1, 10, bag);
        System.out.format("Input: %s%nMissing numbers: %s%nPass count: %d%n",
                Arrays.toString(input), Arrays.toString(output), bag.getPassCount());

        List<Integer> inputList = new ArrayList<>();
        for (int i = 0; i < 10; i++)
            inputList.add(2 * i);
        Collections.shuffle(inputList);
        bag = NumberBag.fromIterable(inputList);
        output = MissingNumbers.find(0, 19, bag);
        System.out.format("%nInput: %s%nMissing numbers: %s%nPass count: %d%n",
                inputList, Arrays.toString(output), bag.getPassCount());

        // Sieve of Eratosthenes
        final int MAXN = 1_000;
        List<Integer> nonPrimes = new ArrayList<>();
        nonPrimes.add(1);
        int[] primes;
        int lastPrimeIndex = 0;
        while (true) {
            primes = MissingNumbers.find(1, MAXN, NumberBag.fromIterable(nonPrimes));
            int p = primes[lastPrimeIndex]; // guaranteed to be prime
            int q = p;
            for (int i = lastPrimeIndex++; i < primes.length; i++) {
                q = primes[i]; // not necessarily prime
                int pq = p * q;
                if (pq > MAXN)
                    break;
                nonPrimes.add(pq);
            }
            if (q == p)
                break;
        }
        System.out.format("%nSieve of Eratosthenes. %d primes up to %d found:%n",
                primes.length, MAXN);
        for (int i = 0; i < primes.length; i++)
            System.out.format(" %4d%s", primes[i], (i % 10) < 9 ? "" : "\n");
    }
}

Las pruebas de matriz grande se pueden realizar de esta manera:

import java.util.*;

public class BatchTest {
    private static final Random rand = new Random();
    public static int MIN_NUMBER = 1;
    private final int minNumber = MIN_NUMBER;
    private final int numberCount;
    private final int[] numbers;
    private int missingCount;
    public long finderTime;

    public BatchTest(int numberCount) {
        this.numberCount = numberCount;
        numbers = new int[numberCount];
        for (int i = 0; i < numberCount; i++)
            numbers[i] = minNumber + i;
    }

    private int passBound() {
        int mBound = missingCount > 0 ? missingCount : 1;
        int nBound = 34 - Integer.numberOfLeadingZeros(numberCount - 1); // ceil(log_2(numberCount)) + 2
        return Math.min(mBound, nBound);
    }

    private void error(String cause) {
        throw new RuntimeException("Error on '" + missingCount + " from " + numberCount + "' test, " + cause);
    }

    // returns the number of times the input array was traversed in this test
    public int makeTest(int missingCount) {
        this.missingCount = missingCount;
        // numbers array is reused when numberCount stays the same,
        // just Fisher–Yates shuffle it for each test
        for (int i = numberCount - 1; i > 0; i--) {
            int j = rand.nextInt(i + 1);
            if (i != j) {
                int t = numbers[i];
                numbers[i] = numbers[j];
                numbers[j] = t;
            }
        }
        final int bagSize = numberCount - missingCount;
        NumberBag inputBag = NumberBag.fromArray(numbers, 0, bagSize);
        finderTime -= System.nanoTime();
        int[] found = MissingNumbers.find(minNumber, minNumber + numberCount - 1, inputBag);
        finderTime += System.nanoTime();
        if (inputBag.getPassCount() > passBound())
            error("too many passes (" + inputBag.getPassCount() + " while only " + passBound() + " allowed)");
        if (found.length != missingCount)
            error("wrong result length");
        int j = bagSize; // "missing" part beginning in numbers
        Arrays.sort(numbers, bagSize, numberCount);
        for (int i = 0; i < missingCount; i++)
            if (found[i] != numbers[j++])
                error("wrong result array, " + i + "-th element differs");
        return inputBag.getPassCount();
    }

    public static void strideCheck(int numberCount, int minMissing, int maxMissing, int step, int repeats) {
        BatchTest t = new BatchTest(numberCount);
        System.out.println("╠═══════════════════════╬═════════════════╬═════════════════╣");
        for (int missingCount = minMissing; missingCount <= maxMissing; missingCount += step) {
            int minPass = Integer.MAX_VALUE;
            int passSum = 0;
            int maxPass = 0;
            t.finderTime = 0;
            for (int j = 1; j <= repeats; j++) {
                int pCount = t.makeTest(missingCount);
                if (pCount < minPass)
                    minPass = pCount;
                passSum += pCount;
                if (pCount > maxPass)
                    maxPass = pCount;
            }
            System.out.format("║ %9d  %9d  ║  %2d  %5.2f  %2d  ║  %11.3f    ║%n", missingCount, numberCount, minPass,
                    (double)passSum / repeats, maxPass, t.finderTime * 1e-6 / repeats);
        }
    }

    public static void main(String[] args) {
        System.out.println("╔═══════════════════════╦═════════════════╦═════════════════╗");
        System.out.println("║      Number count     ║      Passes     ║  Average time   ║");
        System.out.println("║   missimg     total   ║  min  avg   max ║ per search (ms) ║");
        long time = System.nanoTime();
        strideCheck(100, 0, 100, 1, 20_000);
        strideCheck(100_000, 2, 99_998, 1_282, 15);
        MIN_NUMBER = -2_000_000_000;
        strideCheck(300_000_000, 1, 10, 1, 1);
        time = System.nanoTime() - time;
        System.out.println("╚═══════════════════════╩═════════════════╩═════════════════╝");
        System.out.format("%nSuccess. Total time: %.2f s.%n", time * 1e-9);
    }
}

Pruébalos en Ideone

Creo que tengo un algoritmo de O(k)tiempo y O(log(k))espacio, dado que tiene las funciones floor(x)y log2(x)para enteros arbitrariamente grandes disponibles:

Tiene un kentero largo de un bit (de ahí el log8(k)espacio) donde agrega el x^2, donde x es el siguiente número que encuentra en la bolsa: s=1^2+2^2+...esto lleva O(N)tiempo (lo cual no es un problema para el entrevistador). Al final obtienes j=floor(log2(s))cuál es el número más grande que estás buscando. Entonces s=s-jy haces de nuevo lo anterior:

for (i = 0 ; i < k ; i++)
{
  j = floor(log2(s));
  missing[i] = j;
  s -= j;
}

Ahora, por lo general, no tiene las funciones floor y log2 para los 2756enteros -bit, sino para los dobles. ¿Entonces? Simplemente, por cada 2 bytes (o 1, o 3, o 4) puede usar estas funciones para obtener los números deseados, pero esto agrega un O(N)factor a la complejidad del tiempo

Esto puede sonar estúpido, pero, en el primer problema que se le presenta, tendría que ver todos los números restantes en la bolsa para sumarlos y encontrar el número que falta usando esa ecuación.

Entonces, como puede ver todos los números, solo busque el número que falta. Lo mismo ocurre cuando faltan dos números. Bastante simple, creo. No tiene sentido usar una ecuación cuando puedes ver los números restantes en la bolsa.

Creo que esto se puede generalizar así:

Denote S, M como los valores iniciales para la suma de series aritméticas y multiplicación.

S = 1 + 2 + 3 + 4 + ... n=(n+1)*n/2
M = 1 * 2 * 3 * 4 * .... * n 

Debería pensar en una fórmula para calcular esto, pero ese no es el punto. De todos modos, si falta un número, ya proporcionó la solución. Sin embargo, si faltan dos números, denotemos la nueva suma y el múltiplo total por S1 y M1, que serán los siguientes:

S1 = S - (a + b)....................(1)

Where a and b are the missing numbers.

M1 = M - (a * b)....................(2)

Como conoce S1, M1, M y S, la ecuación anterior se puede resolver para encontrar ayb, los números que faltan.

Ahora para los tres números que faltan:

S2 = S - ( a + b + c)....................(1)

Where a and b are the missing numbers.

M2 = M - (a * b * c)....................(2)

Ahora su incógnita es 3, mientras que solo tiene dos ecuaciones que puede resolver.

No sé si esto es eficiente o no, pero me gustaría sugerir esta solución.

1. Calcular xor de los 100 elementos
2. Calcule xor de los 98 elementos (después de eliminar los 2 elementos)
3. Ahora (resultado de 1) XOR (resultado de 2) le da el xor de los dos números faltantes, es decir, XOR b si a y b son los elementos faltantes
   4. Obtenga la suma de los números faltantes con su enfoque habitual de suma la fórmula diff y digamos que la diferencia es d.

Ahora ejecute un bucle para obtener los posibles pares (p, q) que se encuentran en [1, 100] y suman d.

Cuando se obtiene un par, verifique si (resultado de 3) XOR p = q y si es así, hemos terminado.

Corríjame si estoy equivocado y también comente sobre la complejidad del tiempo si esto es correcto

Podemos hacer Q1 y Q2 en O (log n) la mayor parte del tiempo.

Supongamos que nuestro memory chipconsiste en una matriz de nnúmero de test tubes. Y un número xen el tubo de ensayo está representado por x milliliterquímico-líquido.

Supongamos que nuestro procesador es a laser light. Cuando encendemos el láser, atraviesa todos los tubos perpendicularmente a su longitud. Cada vez que pasa a través del líquido químico, la luminosidad se reduce en 1. Y pasar la luz a cierta marca de mililitros es una operación de O(1).

Ahora, si encendemos nuestro láser en el centro del tubo de ensayo y obtenemos la salida de luminosidad

• es igual a un valor precalculado (calculado cuando no faltan números), entonces los números que faltan son mayores que n/2.
• Si nuestra salida es menor, entonces hay al menos un número faltante que es menor que n/2. También podemos verificar si la luminosidad se reduce en 1o 2. si se reduce para 1entonces, un número faltante es menor que n/2y otro es mayor que n/2. Si se reduce para 2entonces, ambos números son más pequeños que n/2.

Podemos repetir el proceso anterior una y otra vez reduciendo nuestro dominio del problema. En cada paso, reducimos el dominio a la mitad. Y finalmente podemos llegar a nuestro resultado.

Algoritmos paralelos que vale la pena mencionar (porque son interesantes),

• ordenar por algún algoritmo paralelo, por ejemplo, la fusión paralela se puede hacer a O(log^3 n)tiempo. Y luego el número faltante se puede encontrar por búsqueda binaria en el O(log n)tiempo.
• Teóricamente, si tenemos nprocesadores, cada proceso puede verificar una de las entradas y establecer un indicador que identifique el número (convenientemente en una matriz). Y en el siguiente paso, cada proceso puede verificar cada indicador y finalmente generar el número que no está marcado. Todo el proceso llevará O(1)tiempo. Tiene O(n)espacio adicional / requisito de memoria.

Tenga en cuenta que los dos algoritmos paralelos proporcionados anteriormente pueden necesitar espacio adicional como se menciona en el comentario .