2^{15} = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 2^{1000}?

*WARNING: This contains the Solution!*

What is your first thought when looking at this problem? Mine was that the largest number that C++ can represent is 2^64 (long long). So obviously we cannot just calculate this by any traditional means.

What I decided to do is go back to grade school and implement some basic arithmetic to solve the problem. I did this by creating a large array that would house the solution. The array was initialized with 1 in the first index and I then preceded to continuously multiply the contents of the array by the base value, 2 in this case. Carrying was of course necessary.

I feel like this was a pretty basic and fairly obvious approach to solving this problem. I know that some of the scripting languages such as Ruby or Python were able to solve this problem in one line - good for them. Here is my code.

#include <iostream>

using std::cout;

using std::endl;

//2^1000 (This solution works for BASE 1-10 & POWER 0+)

const int BASE = 2;

const int POWER = 1000;

int main()

{

//this array size needs to be adjusted according to the BASE and POWER

int number[310];

//BASE^0

number[0] = 1;

int size = 1;

int remainder = 0;

//for each power...

for (int i = 1; i <= POWER; ++i)

{

//raise each value by the base, keep the remainder and use the previous remainder

for (int j = 0; j < size; ++j)

{

//calculate the new remainder

int newRemainder = BASE * number[j] / 10;

//the new value of this digit

number[j] = ((BASE * number[j]) % 10) + remainder;

//check to see if the remainder caused overflow

if (number[j] / 10)

{

newRemainder += number[j] / 10;

number[j] = number[j] % 10;

}

//set the remainder

remainder = newRemainder;

}

//if there is a remainder left then add it and increase the size

if (remainder)

{

number[size] = remainder;

++size;

}

remainder = 0;

}

int sum = 0;

//sum of the digits of the number

for (int i = 0; i < size; ++i)

sum += number[i];

cout << sum << endl;

}

*saved game*

## No comments:

## Post a Comment