n! means n x (n - 1) x ... x 3 x 2 x 1

Find the sum of the digits in the number 100!

*WARNING: This contains the solution!*

This problem was giving me some issues for awhile. I think this is because my planned solution was similar to my solution for Problem 16. However, there are some changes that needed to be made to accommodate multiplication of larger numbers. I was going about this the long hand way and then stumbled upon this.

The example on that page is fairly similar to my approach to problem 16. This example hinted to me the fact that I could allow my carry to be greater than 10. With this hint I was able to quickly implement it into my solution and get the correct answer. Here is the code, which is for the most part the same as problem 16.

#include <iostream>

using std::cout;

using std::endl;

const int FACTORIAL = 100;

int main()

{

int number[200];

number[0] = 1;

int size = 1;

int remainder = 0;

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

{

int carry = 0;

//go through all of the digits

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

{

//the new value of this digit

int digit = number[j] * i + carry;

//calculate the new remainder

carry = digit / 10;

number[j] = digit % 10;

}

//continue to add the carry

while (carry)

{

number[size] = carry % 10;

carry /= 10;

++size;

}

}

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