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

Palindromes en deux bases

Additionner les nombres qui se lisent de la même façon dans les deux sens, en base 10 et dans une seconde base.

Ce que vous allez apprendre

  • Convertir un nombre dans n'importe quelle base
  • Vérifier si une séquence est un palindrome
  • Combiner deux conditions à moindre coût

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

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

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

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.