Problème
Un palindrome se lit de la même façon de gauche à droite et de droite à gauche. 33 est un palindrome en base 10, et en base 2 il s'écrit 100001, encore un palindrome. Additionnez tous les nombres de 1 à limit qui sont des palindromes à la fois en base 10 et en base base. Les nombres s'écrivent sans zéros en tête.
Implémentez double_base_palindromes(limit, base).
Entrée
limit : le plus grand nombre à examiner.
base : la seconde base.
Sortie
Renvoyez la somme de tous ces nombres.
Contraintes
1 ≤ limit ≤ 100 000 ; 2 ≤ base ≤ 16
Exemples
Entrée :
limit = 10
base = 2
Sortie attendue :
expected = 25
Entrée :
long long limit = 10;
long long base = 2;
Sortie attendue :
long long expected = 25;
Entrée :
long limit = 10;
long base = 2;
Sortie attendue :
long expected = 25;
Explication
1, 3, 5, 7 et 9 s'écrivent 1, 11, 101, 111 et 1001 en base 2, tous des palindromes ; ce n'est pas le cas de 2, 4, 6 et 8. Somme 25.
Entrée :
limit = 50
base = 3
Sortie attendue :
expected = 15
Entrée :
long long limit = 50;
long long base = 3;
Sortie attendue :
long long expected = 15;
Entrée :
long limit = 50;
long base = 3;
Sortie attendue :
long expected = 15;
Explication
En base 3 : 1, 2, 4 (11) et 8 (22) conviennent, alors que 33 s'écrit 1020 et 44 s'écrit 1122. Somme 15.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Les divisions successives par la base donnent les chiffres du dernier au premier.
Indice 2
Pour tester un palindrome, comparez la liste des chiffres avec son inverse.
Indice 3
Testez d'abord la base 10 : peu de nombres passent ce test, donc la seconde conversion est rarement nécessaire.
Complexité attendue
temps O(limit × log limit), espace supplémentaire O(log limit)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.