Problème
Élevez le nombre au carré et coupez l'écriture décimale du carré en deux. La partie droite est formée des d derniers chiffres, où d est le nombre de chiffres du nombre de départ, et la partie gauche est ce qui reste (0 s'il ne reste rien). Le nombre est un nombre de Kaprekar si la partie droite n'est pas nulle et si la somme des deux parties redonne le nombre. Par exemple, 297 a 3 chiffres et 297² = 88209. La partie droite est 209, la partie gauche est 88, et 88 + 209 = 297.
Implémentez kaprekar_number(n).
Les définitions varient selon les sources. Ici, la coupure se fait toujours à d chiffres de la droite (c'est la version de la suite A053816 de l'OEIS, et le cas p = d de la définition de Wikipédia). Certaines sources essaient aussi d'autres points de coupure, ce qui accepterait des nombres comme 4879, que cette version rejette. La partie droite peut commencer par des zéros (pour 703, 703² = 494209 donne 494 et 209), et elle ne doit pas être nulle, donc 10, 100, ... ne sont pas des nombres de Kaprekar. 1 est un nombre de Kaprekar, car 1² = 1 donne 0 à gauche et 1 à droite.
Entrée
n : le nombre à tester.
Sortie
Renvoyez true si n est un nombre de Kaprekar selon la définition ci-dessus, sinon false.
Contraintes
1 ≤ n ≤ 10^9
Exemples
Entrée :
n = 45
Sortie attendue :
expected = True
Entrée :
long long n = 45;
Sortie attendue :
bool expected = true;
Entrée :
long n = 45;
Sortie attendue :
bool expected = true;
Explication
45 a 2 chiffres et 45² = 2025. La partie gauche est 20, la partie droite 25, et 20 + 25 = 45, donc la réponse est true.
Entrée :
n = 4879
Sortie attendue :
expected = False
Entrée :
long long n = 4879;
Sortie attendue :
bool expected = false;
Entrée :
long n = 4879;
Sortie attendue :
bool expected = false;
Explication
4879 a 4 chiffres et 4879² = 23804641. La partie gauche est 2380, la partie droite 4641, et 2380 + 4641 = 7021, et non 4879, donc la réponse est false.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Notez d le nombre de chiffres de n et calculez n² dans un entier de 64 bits.
Indice 2
Avec p = 10^d, la partie droite vaut n² mod p et la partie gauche n² / p.
Indice 3
Rejetez le nombre si la partie droite vaut 0, même si la somme correspond.
Complexité attendue
temps O(d) pour un nombre à d chiffres, espace supplémentaire O(1)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.