Esto se puede resolver usando BFS (Breadth First Search). Sea (p, q) un estado que denota un número con una suma de dígitos igual a p y el resto del módulo n igual a q.
De cada estado (p, q) podemos agregar un dígito i a su final y alcanzar el estado (p + i, (q * 10 + i)% n). Por lo tanto, de cada estado, podemos generar otros 10 estados variando i de 0 a 9.
Para cada estado, hacemos un seguimiento del número que agregué al estado anterior para alcanzar ese estado. Esto será necesario en el seguimiento posterior.
- Cómo escribir una matriz de distancia para el algoritmo Bellman Ford
- Inventé un algoritmo de búsqueda de cadenas. ¿Cómo hago para asegurarme de que lleva mi nombre? ¿Es posible patentarlo / copyright o alguna otra cosa? ¿Se pueden proteger los algoritmos?
- ¿Cuál es la complejidad de este algoritmo de conteo de bits?
- Un algoritmo de cifrado de bloque en su forma básica casi nunca se usa para cifrar mensajes largos. ¿Por qué?
- Supongamos que eliminamos un borde de un árbol de expansión y luego agregamos un borde diferente para que permanezca conectado. ¿Seguirá siendo un árbol de expansión?
Por lo tanto, debemos comenzar desde el estado (0,0) y llevar a cabo la búsqueda de amplitud hasta llegar al estado (n, 0). Después de lo cual haremos un retroceso para obtener los dígitos en orden inverso. Asegúrese de usar cadenas aquí, de lo contrario, puede obtener una respuesta incorrecta debido a ceros a la izquierda. 🙂
Aquí está el enlace a mi solución: diptanshu94 / SPOJ-solutions
