Problema
Algunas fracciones unitarias tienen expresión decimal finita (1/4 = 0.25) y las demás se repiten para siempre: 1/6 = 0.1666... repite un bloque de 1 cifra y 1/7 = 0.142857142857... uno de 6. Entre d = 2, 3, ..., limit, encuentra el d cuya fracción 1/d tiene el bloque periódico más largo. Programa la división larga tal como la harías a mano: las cifras empiezan a repetirse en cuanto vuelve a aparecer un resto.
Implementa longest_recurring_cycle(limit).
Entrada
limit: el mayor denominador que hay que probar.
Salida
Devuelve el d con el bloque periódico más largo. Una fracción con decimal finito tiene un bloque de longitud 0. Si hay empate, devuelve el menor d.
Restricciones
2 ≤ limit ≤ 2000
Ejemplos
Entrada:
limit = 8
Salida esperada:
expected = 7
Entrada:
long long limit = 8;
Salida esperada:
long long expected = 7;
Entrada:
long limit = 8;
Salida esperada:
long expected = 7;
Explicación
Las longitudes de los periodos para 2 a 8 son 0, 1, 0, 0, 1, 6, 0, así que la respuesta es 7.
Entrada:
limit = 5
Salida esperada:
expected = 3
Entrada:
long long limit = 5;
Salida esperada:
long long expected = 3;
Entrada:
long limit = 5;
Salida esperada:
long expected = 3;
Explicación
1/3 repite una cifra, mientras que 1/2, 1/4 y 1/5 son finitas, así que la respuesta es 3.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Cada nueva cifra de 1/d se obtiene del resto multiplicado por 10.
Pista 2
Recuerda en qué paso apareció cada resto por primera vez.
Pista 3
Si el resto se vuelve 0, el decimal es finito; si no, la longitud del ciclo es la distancia entre dos apariciones del mismo resto.
Complejidad esperada
tiempo O(limit²), espacio extra O(limit)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.