1358. Digit Sum of a Power of Two
Print the sum of the decimal digits of 2^n.
2^10 = 1024 -> 7
2^15 = 32768 -> 26
2^100 -> 115
At n = 10000 the value has 3011 digits, so it must be held as an array of
digits rather than a number. There is no shortcut: the digit sum of a power of
two follows no pattern, which is exactly why the question is asked.
Doubling a digit array is short. Walk it from the least significant end:
for each digit:
d = digit * 2 + carry
digit = d % 10
carry = d / 10
while carry: append carry % 10, carry /= 10
Repeat n times and add the digits. That is about 10000 * 3011 elementary
steps, which is fast.
Storing the digits least significant FIRST is what makes this tidy: growth happens by appending at the end rather than inserting at the front, and the carry loop falls out naturally. Storing them the human way round forces a shift on every growth step.
n = 0 gives 2^0 = 1, so the answer is 1 and the loop runs zero times.
Constraints - `0 ≤ n ≤ 10000`
Input
One line containing the integer n.
Output
Print the sum of the decimal digits of 2^n.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.