¿Qué es un algoritmo para encontrar el número N de base 10 más pequeño, mayor que la entrada, de modo que N se escriba con todos los 1 y 0 y la entrada sea un factor de N?

Answer 1

Si el número dado n se factoriza como
[matemáticas] n = 2 ^ a5 ^ bm [/ matemáticas]
donde m no es divisible por 2 o 5. Ahora podemos simplificar el problema para resolver solo por m . El múltiplo final cero uno debe tener potencias iguales de 2 y 5 en su factorización. De lo contrario, el último dígito antes de los ceros finales será 2, 4, 5, 6 u 8. Entonces, si el múltiplo cero más pequeño de m es q, y c = max ( a, b ), entonces el múltiplo cero más pequeño de n es [matemáticas] N = 10 ^ cq [/ matemáticas].

A continuación, intentaré esbozar un algoritmo para la parte m . Queremos encontrar un conjunto de potencias distintas de 10 para que su suma sea divisible por m . Entonces podemos encontrar los restos que quedan por cada potencia de 10. Luego tenemos que elegir esas potencias para que sus restos sumen un múltiplo de m . Como ejemplo, echemos un vistazo a 7. Los restos que quedan 1, 10, 100, … son 1, 3, 2, 6, 4, …. Podemos ver que 1 + 6 = 7. Por lo tanto, 1001 es un múltiplo de 7. Este paso se puede realizar mediante programación dinámica haciendo un seguimiento de los posibles restos y sumas restantes después de cada potencia de diez.

Answer 2

Tengo una solución O (N ^ 3) DP.

1. Un [0..N-1] es una matriz booleana. A [i] es verdadero al final del paso k significa que hay un número m con k o menos dígitos 0/1 donde m tiene un recordatorio de i cuando lo dividimos por N.
2. Comience con c = 1 y todo A sea falso.
3. Para k = 1 como máximo N * N do
4. Deje que la matriz B sea una copia de A.
5. B [c] = verdadero
6. Para 0 <= i
7. Si A [i] es cierto, entonces
8. B [(c + i)% N] = verdadero
9. Copia B en A.
10. Si A [0] es verdadero, ¡entonces has encontrado la respuesta!
11. De lo contrario, c = (c * 10)% N y continúa el ciclo de k

No voy a escribir ninguna pista sobre qué, cómo o por qué, simplemente porque eso arruinaría lo menos posible. Por supuesto, si no sabes DP, ve a aprenderlo primero.

Answer 3

Incremente en 1 hasta que el último dígito sea igual a 0 o 1
Incremente en 10 hasta que el penúltimo dígito sea igual a 0 o 1
Incremente en 100 hasta que el penúltimo dígito sea igual a 0 o 1
…
Incremente en cualquier potencia de 10 el primer dígito es hasta que el primer dígito sea igual a 1 o 10.

Answer 4

O (1) solución.

Veo muchas respuestas complicadas aquí. Si se trata básicamente de entradas positivas, básicamente haría un desplazamiento a la izquierda de la posición del valor de entrada de base 2 1, ya que la siguiente N inmediata para su entrada sería el doble de la entrada en la base 2. La complejidad del algoritmo es del orden de O (1).