Problema
Na base b, um número é escrito com os dígitos de 0 a b − 1, e as letras de A a Z representam os valores de 10 a 35. Assim, FF na base 16 vale 255, que é 377 na base 8 e 11111111 na base 2. Converta digits, escrito na base from_base, para o mesmo número escrito na base to_base.
Implemente base_converter(digits, from_base, to_base).
Entrada
digits: o número na base from_base: uma string não vazia de dígitos e letras maiúsculas, cada um menor que from_base. Pode ter zeros à esquerda.
from_base: a base da entrada.
to_base: a base do resultado.
Saída
Retorne o número na base to_base usando 0-9 e as maiúsculas A-Z, sem zeros à esquerda. O zero é retornado como "0".
Restrições
2 ≤ from_base, to_base ≤ 36
O valor do número é no máximo 10^18.
Exemplos
Entrada:
digits = "FF"
from_base = 16
to_base = 8
Saída esperada:
expected = "377"
Entrada:
std::string digits = "FF";
long long from_base = 16;
long long to_base = 8;
Saída esperada:
std::string expected = "377";
Entrada:
string digits = "FF";
long from_base = 16;
long to_base = 8;
Saída esperada:
string expected = "377";
Explicação
FF é 15 × 16 + 15 = 255, e 255 = 3 × 64 + 7 × 8 + 7, então a resposta é "377".
Entrada:
digits = "1010"
from_base = 2
to_base = 36
Saída esperada:
expected = "A"
Entrada:
std::string digits = "1010";
long long from_base = 2;
long long to_base = 36;
Saída esperada:
std::string expected = "A";
Entrada:
string digits = "1010";
long from_base = 2;
long to_base = 36;
Saída esperada:
string expected = "A";
Explicação
1010 em binário é 10, que na base 36 é o único dígito "A".
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Percorra a entrada da esquerda para a direita, multiplicando o valor acumulado por from_base e somando cada dígito.
Dica 2
Para escrever o resultado, pegue os restos da divisão por to_base; eles saem do último dígito para o primeiro.
Dica 3
Trate o zero como caso especial, para que a saída seja "0" e não vazia.
Complexidade esperada
tempo O(L), espaço extra O(L), em que L é a quantidade de dígitos
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.