Saturday, July 18, 2009

Grind Report 20

Problem 20

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