Problem 016

Project Euler

Power digit sum

Problem 16

215 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 21000?

In additional to use recursion, a very fundamental strategy call divide & conquer method can be used in here to minimize the number of time to do multiplication. Note that 2^{1000} = 2^{500} \cdot 2^{500}, splitting the exponent each time and multiply itself will cut the multiplication by half. However, the number of digits for the answer is long (> 300 digits), using an array of integer (or char) is a must without special library and cause the multiplication of two long digits values quite cumbersome at each stage. Therefore, the solution seems to be easier to iteratively multiply 2 for 1000 time onto the interim result.