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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s