Grind Report 16

Problem 16

2¹⁵ = 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¹⁰⁰⁰?

*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*