В системе счисления с основанием b число записывается цифрами от 0 до b − 1, причём буквы от A до Z обозначают цифры со значениями от 10 до 35. Так, FF в шестнадцатеричной системе - это 255, в восьмеричной это 377, а в двоичной 11111111. Переведите число digits, записанное в системе с основанием from_base, в систему с основанием to_base.
Реализуйте base_converter(digits, from_base, to_base).
Входные данные
digits: число в системе from_base, непустая строка из цифр и заглавных букв, каждая из которых меньше from_base. Возможны ведущие нули.
from_base: основание исходной системы.
to_base: основание системы для результата.
Выходные данные
Верните число в системе to_base, используя 0-9 и заглавные A-Z, без ведущих нулей. Ноль возвращается как "0".
Ограничения
2 ≤ from_base, to_base ≤ 36
Значение числа не превышает 10^18.
Примеры
Ввод:
digits = "FF"
from_base = 16
to_base = 8
Ожидаемый вывод:
expected = "377"
Ввод:
std::string digits = "FF";
long long from_base = 16;
long long to_base = 8;
Ожидаемый вывод:
std::string expected = "377";
Ввод:
string digits = "FF";
long from_base = 16;
long to_base = 8;
Ожидаемый вывод:
string expected = "377";
Пояснение
FF = 15 × 16 + 15 = 255, а 255 = 3 × 64 + 7 × 8 + 7, поэтому ответ "377".
Ввод:
digits = "1010"
from_base = 2
to_base = 36
Ожидаемый вывод:
expected = "A"
Ввод:
std::string digits = "1010";
long long from_base = 2;
long long to_base = 36;
Ожидаемый вывод:
std::string expected = "A";
Ввод:
string digits = "1010";
long from_base = 2;
long to_base = 36;
Ожидаемый вывод:
string expected = "A";
Пояснение
1010 в двоичной системе - это 10, то есть одна цифра "A" в системе с основанием 36.
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Проходите входную строку слева направо, умножая текущее значение на from_base и прибавляя очередную цифру.
Подсказка 2
Чтобы записать результат, берите остатки от деления на to_base; они получаются начиная с последней цифры.
Подсказка 3
Обработайте ноль отдельно, чтобы результат был "0", а не пустой строкой.
Ожидаемая сложность
время O(L), доп. память O(L), где L - количество цифр
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.