Problème
En base b, un nombre s'écrit avec les chiffres de 0 à b − 1, les lettres de A à Z représentant les valeurs 10 à 35. Ainsi, FF en base 16 vaut 255, ce qui s'écrit 377 en base 8 et 11111111 en base 2. Convertissez digits, écrit en base from_base, en ce même nombre écrit en base to_base.
Implémentez base_converter(digits, from_base, to_base).
Entrée
digits : le nombre en base from_base, une chaîne non vide de chiffres et de lettres majuscules, chacun inférieur à from_base. Elle peut commencer par des zéros.
from_base : la base de l'entrée.
to_base : la base du résultat.
Sortie
Renvoyez le nombre en base to_base avec les caractères 0-9 et les majuscules A-Z, sans zéros en tête. Zéro est renvoyé sous la forme "0".
Contraintes
2 ≤ from_base, to_base ≤ 36
La valeur du nombre est au plus 10^18.
Exemples
Entrée :
digits = "FF"
from_base = 16
to_base = 8
Sortie attendue :
expected = "377"
Entrée :
std::string digits = "FF";
long long from_base = 16;
long long to_base = 8;
Sortie attendue :
std::string expected = "377";
Entrée :
string digits = "FF";
long from_base = 16;
long to_base = 8;
Sortie attendue :
string expected = "377";
Explication
FF vaut 15 × 16 + 15 = 255, et 255 = 3 × 64 + 7 × 8 + 7, donc la réponse est "377".
Entrée :
digits = "1010"
from_base = 2
to_base = 36
Sortie attendue :
expected = "A"
Entrée :
std::string digits = "1010";
long long from_base = 2;
long long to_base = 36;
Sortie attendue :
std::string expected = "A";
Entrée :
string digits = "1010";
long from_base = 2;
long to_base = 36;
Sortie attendue :
string expected = "A";
Explication
1010 en binaire vaut 10, ce qui s'écrit avec le seul chiffre "A" en base 36.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Parcourez l'entrée de gauche à droite en multipliant la valeur courante par from_base puis en ajoutant chaque chiffre.
Indice 2
Pour écrire le résultat, prenez les restes des divisions par to_base ; ils sortent en commençant par le dernier chiffre.
Indice 3
Traitez zéro à part pour que la sortie soit "0" et non une chaîne vide.
Complexité attendue
temps O(L), espace supplémentaire O(L), où L est le nombre de chiffres
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.