Todos los desafíos
Difícil 0 resueltos 0% de aceptación

El periodo decimal más largo

Encuentra el d, hasta un límite, cuya fracción 1/d tiene el periodo decimal más largo.

Lo que aprenderás

  • Simular la división larga con restos
  • Detectar una repetición con una tabla de consulta
  • Obtener la longitud de un ciclo a partir de las primeras apariciones

Problema

Ver original (inglés)

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

Ejemplo 1
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.

Ejemplo 2
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.

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

Aún no hay soluciones aprobadas. Resuélvelo y quédate el primer puesto.

Aprende de otros

Soluciones de la comunidad

Aún no hay soluciones publicadas. Resuelve este reto para compartir la primera.