Problème
Certaines fractions unitaires ont un développement décimal fini (1/4 = 0,25), les autres se répètent à l'infini : 1/6 = 0,1666... a une période de 1 chiffre et 1/7 = 0,142857142857... une période de 6. Parmi d = 2, 3, ..., limit, trouvez le d pour lequel 1/d a la plus longue période. Programmez la division posée : les chiffres se répètent dès qu'un reste réapparaît.
Implémentez longest_recurring_cycle(limit).
Entrée
limit : le plus grand dénominateur à essayer.
Sortie
Renvoyez le d dont la période est la plus longue. Une fraction au développement fini a une période de longueur 0. En cas d'égalité, renvoyez le plus petit d.
Contraintes
2 ≤ limit ≤ 2000
Exemples
Entrée :
limit = 8
Sortie attendue :
expected = 7
Entrée :
long long limit = 8;
Sortie attendue :
long long expected = 7;
Entrée :
long limit = 8;
Sortie attendue :
long expected = 7;
Explication
Pour d de 2 à 8, les longueurs de période sont 0, 1, 0, 0, 1, 6, 0, donc la réponse est 7.
Entrée :
limit = 5
Sortie attendue :
expected = 3
Entrée :
long long limit = 5;
Sortie attendue :
long long expected = 3;
Entrée :
long limit = 5;
Sortie attendue :
long expected = 3;
Explication
1/3 répète un chiffre, tandis que 1/2, 1/4 et 1/5 ont un développement fini, donc la réponse est 3.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Chaque nouveau chiffre de 1/d s'obtient à partir du reste multiplié par 10.
Indice 2
Retenez l'étape à laquelle chaque reste est apparu pour la première fois.
Indice 3
Si le reste devient 0, le développement est fini ; sinon, la longueur du cycle est l'écart entre deux apparitions du même reste.
Complexité attendue
temps O(limit²), espace supplémentaire O(limit)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.