Dada una matriz bidimensional kx ((26^k)-1) , que contiene todas las cadenas posibles de letras mayúsculas de longitud k , excepto una de ellas. ¿Cómo podemos saber la cadena que falta mientras leemos solo las entradas theta(26^k) de la matriz, y no las entradas theta(kx (26^k))?
Hemos pensado en usar punteros 'k' para todas las columnas 26^k, pero seguirá siendo lo mismo que buscar entradas kx 26^k, también consideramos buscar a[:0], a[:1], a [:2], . . . a[:(26^k)-1] pero sigue siendo lo mismo que buscar valores de kx 26^k, ya que el corte también cuenta como mirar esas entradas.
Aquí hay una manera de hacerlo en una complejidad de tiempo Θ(26^k) usando un espacio O(26^k) adicional.
Veamos primero la intuición:
(26^k)-1 entradas. En la primera fila, todas las letras tendrían la misma frecuencia excepto una cuya frecuencia sería una menor que las otras 25. Esta letra sería la primera letra de nuestra cadena faltante.26^(k-1) - 1 columnas para las cuales el valor correspondiente de la primera fila era la letra que faltaba (pero ahora, para saber qué columnas buscar, necesitaríamos almacenar esas columnas en otro lugar usando espacio adicional). Y solo tendríamos que buscar en 26^(k-1) - 1 entradas en la segunda fila.O(no. of entries) y el espacio constante (26 letras). Una vez que conocemos la letra que falta en una fila dada, podemos revisar la fila nuevamente y almacenar índices de todas las columnas para las cuales la letra es la letra que falta y almacenar esos índices en una matriz separada usando el espacio adicional O(26^(k-1-i)) para ith fila.26^(k-2) - 1 entradas para los índices que almacenamos en nuestra matriz cuando miramos la segunda fila.Así que el número total. de las entradas que tendríamos que mirar en cada fila (después de resumir la serie geométrica) serían:
sum{(26 - 1), (26^2 - 1), (26^3 - 1) ... (26^k -1)} = (26*(1 - (26^k))/(1-26) - k que es Θ(26^k) complejidad de tiempo y espacio.