Problème
Additionnez les chiffres de n. Si le résultat comporte plus d'un chiffre, additionnez à nouveau ses chiffres. Répétez l'opération jusqu'à ce qu'il ne reste qu'un seul chiffre.
Implémentez digital_root(n).
Entrée
n : Un entier positif.
Sortie
Retournez le chiffre final obtenu.
Contraintes
1 ≤ n ≤ 10¹⁸
Exemples
Exemple 1
Entrée :
n = 999
Sortie attendue :
expected = 9Entrée :
long long n = 999;
Sortie attendue :
long long expected = 9;Entrée :
long n = 999;
Sortie attendue :
long expected = 9;Explication
9 + 9 + 9 = 27, puis 2 + 7 = 9.
Exemple 2
Entrée :
n = 38
Sortie attendue :
expected = 2Entrée :
long long n = 38;
Sortie attendue :
long long expected = 2;Entrée :
long n = 38;
Sortie attendue :
long expected = 2;Explication
3 + 8 = 11, puis 1 + 1 = 2.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Additionner les chiffres plusieurs fois finit par réduire le nombre à un seul chiffre.
Indice 2
Tu peux simuler les sommes répétées jusqu’à ce que la valeur soit inférieure à 10.
Indice 3
Attention aux très grandes entrées ; le processus est simple, mais les passages répétés sur les chiffres font l’essentiel du travail.
Complexité attendue
temps O(d log n), espace supplémentaire O(1)