arrays algorithm data-structures dynamic-programming subset-sum

arrays - Número más pequeño que no se puede formar a partir de la suma de números de la matriz



algorithm data-structures (4)

Considere todos los enteros en el intervalo [2 i .. 2 i + 1 - 1]. Y suponga que todos los enteros inferiores a 2 i pueden formarse a partir de la suma de números de la matriz dada. Supongamos también que ya conocemos C, que es la suma de todos los números por debajo de 2 i . Si C> = 2 i + 1 - 1, cada número en este intervalo puede representarse como la suma de los números dados. De lo contrario, podríamos verificar si el intervalo [2 i .. C + 1] contiene algún número de la matriz dada. Y si no hay tal número, C + 1 es lo que buscamos.

Aquí hay un bosquejo de un algoritmo:

  1. Para cada número de entrada, determine a qué intervalo pertenece y actualice la suma correspondiente: S[int_log(x)] += x .
  2. Calcular la suma de prefijos para la matriz S: foreach i: C[i] = C[i-1] + S[i] .
  3. Filtre la matriz C para mantener solo las entradas con valores inferiores a la siguiente potencia de 2.
  4. Escanee la matriz de entrada una vez más y observe cuál de los intervalos [2 i .. C + 1] contiene al menos un número de entrada: i = int_log(x) - 1; B[i] |= (x <= C[i] + 1) i = int_log(x) - 1; B[i] |= (x <= C[i] + 1) .
  5. Encuentre el primer intervalo que no se filtra en el paso # 3 y el elemento correspondiente de B[] no se establece en el paso # 4.

Si no es obvio por qué podemos aplicar el paso 3, aquí está la prueba. Elija cualquier número entre 2 i y C, luego reste secuencialmente todos los números debajo de 2 i en orden decreciente. Eventualmente obtenemos un número menor que el último número restado o cero. Si el resultado es cero, simplemente sume todos los números restados y tenemos la representación del número elegido. Si el resultado es distinto de cero y menor que el último número restado, este resultado también es menor que 2 i , por lo que es "representable" y ninguno de los números restados se utiliza para su representación. Cuando volvemos a sumar estos números restados, tenemos la representación del número elegido. Esto también sugiere que, en lugar de filtrar los intervalos uno por uno, podríamos omitir varios intervalos a la vez saltando directamente a int_log de C.

La complejidad del tiempo está determinada por la función int_log() , que es un logaritmo entero o un índice del bit de conjunto más alto en el número. Si nuestro conjunto de instrucciones contiene logaritmo de enteros o su equivalente (cuente los ceros iniciales o trucos con números de punto flotante), entonces la complejidad es O (n). De lo contrario, podríamos usar un poco de pirateo para implementar int_log() en O (log log U) y obtener O (n * log log U) complejidad de tiempo. (Aquí U es el número más grande en la matriz).

Si el paso 1 (además de actualizar la suma) también actualizará el valor mínimo en un rango determinado, ya no es necesario el paso 4. Podríamos simplemente comparar C [i] con Min [i + 1]. Esto significa que solo necesitamos una sola pasada sobre la matriz de entrada. O podríamos aplicar este algoritmo no a una matriz, sino a un flujo de números.

Varios ejemplos:

Input: [ 4 13 2 3 1] [ 1 2 3 9] [ 1 1 2 9] int_log: 2 3 1 1 0 0 1 1 3 0 0 1 3 int_log: 0 1 2 3 0 1 2 3 0 1 2 3 S: 1 5 4 13 1 5 0 9 2 2 0 9 C: 1 6 10 23 1 6 6 15 2 4 4 13 filtered(C): n n n n n n n n n n n n number in [2^i..C+1]: 2 4 - 2 - - 2 - - C+1: 11 7 5

Para los números de entrada de precisión múltiple, este enfoque necesita tiempo O (n * log M) y espacio O (log M). Donde M es el número más grande en la matriz. Se necesita el mismo tiempo solo para leer todos los números (y en el peor de los casos necesitamos cada parte de ellos).

Aún así, este resultado puede mejorarse a O (n * log R) donde R es el valor encontrado por este algoritmo (en realidad, la variante sensible a la salida). La única modificación necesaria para esta optimización es en lugar de procesar números enteros a la vez, procesarlos dígito a dígito: la primera pasada procesa los bits de orden inferior de cada número (como los bits 0..63), la segunda pasada - los bits siguientes (como 64..127), etc. Podríamos ignorar todos los bits de orden superior después de encontrar el resultado. Esto también reduce los requisitos de espacio a los números O (K), donde K es el número de bits en palabra de máquina.

Este problema me fue preguntado en una entrevista de Amazon.

Dado un conjunto de enteros positivos, tiene que encontrar el entero positivo más pequeño que no se puede formar a partir de la suma de números de un conjunto.

Ejemplo:

Array:[4 13 2 3 1] result= 11 { Since 11 was smallest positive number which can not be formed from the given array elements }


Lo que hice fue:

  1. ordenó la matriz
  2. calculó la suma del prefijo
  3. Pase por la matriz de suma y verifique si el siguiente elemento es menor que 1 mayor que la suma, es decir, A [j] <= (suma + 1). Si no es así, entonces la respuesta sería suma + 1

Pero esta era la solución nlog (n).

El entrevistador no estaba satisfecho con esto y pidió una solución en menos de O (n log n).

Hay un hermoso algoritmo para resolver este problema en el tiempo O (n + Ordenar), donde Ordenar es la cantidad de tiempo requerido para ordenar la matriz de entrada.

La idea detrás del algoritmo es ordenar la matriz y luego hacer la siguiente pregunta: ¿cuál es el número entero positivo más pequeño que no puede hacer usando los primeros k elementos de la matriz? Luego, avanza por la matriz de izquierda a derecha, actualizando su respuesta a esta pregunta, hasta que encuentre el número más pequeño que no puede hacer.

Así es como funciona. Inicialmente, el número más pequeño que no puede hacer es 1. Luego, de izquierda a derecha, haga lo siguiente:

  • Si el número actual es más grande que el número más pequeño que no puedes obtener hasta el momento, entonces sabes el número más pequeño que no puedes hacer: es el que tienes registrado y listo.
  • De lo contrario, el número actual es más pequeño que el número más pequeño que no puede hacer. La afirmación es que sí puede hacer este número. En este momento, usted sabe el número más pequeño que no puede hacer con los primeros k elementos de la matriz (llámelo candidate ) y ahora está mirando el valor A[k] . El número candidate - A[k] por lo tanto, debe ser un número que pueda hacer con los primeros k elementos de la matriz, ya que de lo contrario candidate - A[k] sería un número menor que el número más pequeño que supuestamente no puede hacer con los primeros k números en la matriz. Además, puede hacer que cualquier número en el rango sea candidate a candidate + A[k] , inclusive, porque puede comenzar con cualquier número en el rango de 1 a A[k] , inclusive, y luego agregar candidate - 1 al mismo. Por lo tanto, establezca al candidate a candidate + A[k] e incremente k .

En pseudocódigo:

Sort(A) candidate = 1 for i from 1 to length(A): if A[i] > candidate: return candidate else: candidate = candidate + A[i] return candidate

Aquí hay una prueba de funcionamiento en [4, 13, 2, 1, 3] . Ordena la matriz para obtener [1, 2, 3, 4, 13] . Luego, establezca el candidate a 1. Luego hacemos lo siguiente:

  • A [1] = 1, candidate = 1:
    • A [1] ≤ candidate , así que establece candidate = candidate + A[1] = 2
  • A [2] = 2, candidate = 2:
    • A [2] ≤ candidate , así que establece candidate = candidate + A[2] = 4
  • A [3] = 3, candidate = 4:
    • A [3] ≤ candidate , así que establece candidate = candidate + A[3] = 7
  • A [4] = 4, candidate = 7:
    • A [4] ≤ candidate , así que establece candidate = candidate + A[4] = 11
  • A [5] = 13, candidate = 11:
    • A [4]> candidate , entonces devuelva candidate (11).

Así que la respuesta es 11.

El tiempo de ejecución aquí es O (n + Ordenar) porque fuera de la clasificación, el tiempo de ejecución es O (n). Puede clasificar claramente el tiempo O (n log n) utilizando heapsort, y si conoce algún límite superior en los números, puede clasificar el tiempo O (n log U) (donde U es el número máximo posible) utilizando la ordenación por radix. Si U es una constante fija (por ejemplo, 10 9 ), entonces la ordenación de radix se ejecuta en el tiempo O (n) y todo este algoritmo se ejecuta también en el tiempo O (n).

¡Espero que esto ayude!

Usa bitvectors para lograr esto en tiempo lineal.

Comience con un bitvector vacío b. Luego, para cada elemento k en tu matriz, haz esto:

b = b | b << k | 2 ^ (k-1)

Para que quede claro, el elemento i''th se establece en 1 para representar el número i, y | k | k está configurando el elemento k-th en 1.

Después de que termine de procesar la matriz, el índice del primer cero en b es su respuesta (contando desde la derecha, comenzando en 1).

  1. b = 0
  2. proceso 4: b = b | b << 4 | 1000 = 1000
  3. proceso 13: b = b | b << 13 | 1000000000000 = 10001000000001000
  4. proceso 2: b = b | b << 2 | 10 = 1010101000000101010
  5. proceso 3: b = b | b << 3 | 100 = 1011111101000101111110
  6. proceso 1: b = b | b << 1 | 1 = 11111111111001111111111

Primer cero: posición 11.