Степени двойки растут быстро: в 2^64 уже 20 цифр, а в 2^2000 больше 600. Вычислите 2^n точно и сложите его десятичные цифры. Если в языке нет длинной арифметики, храните число как массив цифр и удвойте его n раз.
Реализуйте digit_sum_power_of_two(n).
Входные данные
n: показатель степени.
Выходные данные
Верните сумму десятичных цифр числа 2^n.
Ограничения
0 ≤ n ≤ 2000
Примеры
Ввод:
n = 10
Ожидаемый вывод:
expected = 7
Ввод:
long long n = 10;
Ожидаемый вывод:
long long expected = 7;
Ввод:
long n = 10;
Ожидаемый вывод:
long expected = 7;
Пояснение
2^10 = 1024, и 1 + 0 + 2 + 4 = 7.
Ввод:
n = 0
Ожидаемый вывод:
expected = 1
Ввод:
long long n = 0;
Ожидаемый вывод:
long long expected = 1;
Ввод:
long n = 0;
Ожидаемый вывод:
long expected = 1;
Пояснение
2^0 = 1, поэтому сумма цифр равна 1.
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
2^n - это 1, удвоенная n раз.
Подсказка 2
Храните цифры, начиная с младшей, чтобы переносы сдвигались к концу массива.
Подсказка 3
Складывайте цифры только после того, как удвоение закончено.
Ожидаемая сложность
время O(n²), доп. память O(n)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.