Tous les défis
Difficile 0 résolus 0 % de réussite

Plus longue période décimale

Trouver le d, jusqu'à une limite, pour lequel la fraction 1/d a la plus longue période décimale.

Ce que vous allez apprendre

  • Simuler une division posée à l'aide des restes
  • Détecter une répétition avec une table de correspondance
  • Déduire la longueur d'un cycle des premières positions

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

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

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

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

Aucune solution validée pour l'instant. Résolvez-le et prenez la première place.

Apprenez des autres

Solutions de la communauté

Aucune solution publiée pour l'instant. Résolvez ce défi pour partager la première.