Project Euler problem 20. Getting wrong answer

[Meden]

My code seems to work fine as I carefully step through it in the debugger, but I have a mistake I can't find. Does someone see it?

As far as my approach goes, I realize I could download a big number library, but I wanted to use my own base operations instead. I had used a ten base strategy for a previous problem, and half way through it I realized it would have been better if it instead used a large number base instead.

Project Euler problem 20: https://projecteuler.net/problem=20
"n! means n × (n − 1) × ... × 3 × 2 × 1

For example, 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800,
and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.

Find the sum of the digits in the number 100!"

#include <iostream>
#include <vector>
#include <algorithm>

void factorialExpansion(unsigned int& nextN, unsigned int base, unsigned long long& power16, std::vector<unsigned long long>& factorial);

int main() {
	// limit!
	const unsigned int limit = 100;

	std::vector<unsigned long long>factorial = { 1 };
	unsigned int base = 0;

	{
		unsigned int nextN = limit;
		unsigned int carry = 0;
		unsigned long long power16 = static_cast<unsigned long long>(pow(10, 16));

		while (nextN > 1) {
			factorialExpansion(nextN, base, power16, factorial);
			nextN--;
		}
	}

	// sum factorial digits
	unsigned int sum = 0;
	while (base < factorial.size()) {
		while (factorial[base] >= 1) {
			sum += factorial[base] % 10;
			factorial[base] /= 10;
		}
		base++;
	}

	std::cout << "Answer: " << sum << std::endl;
	
	std::cout << std::endl;
}

void factorialExpansion(unsigned int& nextN, unsigned int base, unsigned long long& power16, std::vector<unsigned long long>& factorial) {
	// multiply current base
	factorial[base] *= nextN;

	// if current base becomes too large
	if (factorial[base] > power16) {

		// pop off the largest part, and save it in carry
		unsigned int carry = static_cast<unsigned int>(factorial[base] / power16);
		factorial[base] %= power16;

		// if next base does not yet exist, create it and put carry inside
		if (base + 2 > factorial.size()) {
			factorial.push_back(carry);
		}
		// if next base exists, continue multiply operation on it before adding carry
		else {
			base++;
			factorialExpansion(nextN, base, power16, factorial);
			factorial[base] += carry;
		}
	}
}

The answer my code produces is 423. The correct answer is 648.

[lastchance]

Your digits are decimal digits - what are you trying to achieve by using some higher base?

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

//======================================================================

class BigInt
{
public:
   vector<int> digits;                 // note: digits stored in REVERSE order

   BigInt( int n = 0 );
};


BigInt::BigInt( int n )                // Construct from non-negative integer
{
   if ( n == 0 )
   {
      digits.push_back( 0 );
   }
   else
   {
      while ( n > 0 )
      {
         digits.push_back( n % 10 );
         n /= 10;
      }
   }
}

BigInt operator*( const BigInt &a, int n )
{
   BigInt result;
   result.digits.clear();
   int asize = a.digits.size();
   int i = 0;
   int carry = 0;
   while ( i < asize || carry > 0 )
   {
      if ( i < asize ) carry += n * a.digits[i];
      int digit = carry % 10;
      carry /= 10;
      result.digits.push_back( digit );
      i++;
   }
   return result;
}

ostream &operator<<( ostream &stream, const BigInt &a )
{
   for ( int i = a.digits.size() - 1; i >= 0; i-- ) stream << a.digits[i];
   return stream;
}

//======================================================================

int main()
{
   BigInt I = 1;
   for ( int j = 2; j <= 100; j++ ) I = I * j;
   cout << "100! = " << I << '\n';
   cout << "Sum of digits = " << accumulate( I.digits.begin(), I.digits.end(), 0 ) << '\n';
}

100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
Sum of digits = 648

[dhayden]

Something is wrong with your calculations. Change limit 10 19 and print out the factorial values and you'll see that you have the wrong answer.

[lastchance]

@meden,

What happens if your line 45 logical statement is false? You aren't at present multiplying the higher parts of the factorial, so your overall factorial will end up too small.

Your lines 42 to 61 should roughly parallel my lines 38 to 47, the only difference being that you are working to base "power16" and I was working to base 10. I guess you can, in principle, do most loops by recursion - but I'm not sure that it's helping you here.

[48T7M4Gy]

#include <iostream>

int main(){
    const int LIMIT = 200;
    int a[LIMIT] = {0}, sum = 0, carryover = 0, temp;
    a[0] = 1;
    for ( int factor = 1; factor < 101; factor++){
        for(int i = 0; i < LIMIT ; i++){
            temp = a[i] * factor + carryover;
            a[i] = temp % 10;
            carryover = temp /10;
        }
    }
    
    for (int i = 0; i < LIMIT; i++){
        sum += a[i];
        std::cout << a[LIMIT - i - 1];
    }
    
    std::cout << std::endl << "Answer = " << sum + carryover;
    return 0;
}

[lastchance]

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

vector<int> Factorial( int n )
{
   if ( n == 1 ) return vector<int>{ 1 };

   vector<int> result, last = Factorial( n - 1 );
   int size = last.size(), i = 0, carry = 0;
   while ( i < size || carry > 0 )
   {
      if ( i < size ) carry += n * last[i];
      result.push_back( carry % 10 );
      carry /= 10;
      i++;
   }
   return result;
}

int main()
{
   vector<int> F = Factorial( 100 );
   for ( int j = F.size() - 1; j >= 0; j-- ) cout << F[j];
   cout << "\nSum of digits = " << accumulate( F.begin(), F.end(), 0 ) << '\n';
}

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
Sum of digits = 648

@meden, if you want to, you can use your 10^16 base instead as below. Outputting the factorial and adding the digits becomes more tricky, that's all.

#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;

typedef unsigned long long INT;
const INT POWER = 10000000000000000;    // 10^16
const int WIDTH = 16;                   // needed to output the factorial sensibly

//======================================================================

int sumDigits( INT n ) { return ( n == 0 ? 0 : sumDigits( n / 10 ) + n % 10 ); }

//======================================================================

vector<INT> Factorial( int n )
{
   if ( n == 1 ) return vector<INT>{ 1 };

   vector<INT> result, last = Factorial( n - 1 );
   INT size = last.size(), i = 0, carry = 0;
   while ( i < size || carry > 0 )
   {
      if ( i < size ) carry += n * last[i];
      result.push_back( carry % POWER );
      carry /= POWER;
      i++;
   }
   return result;
}

//======================================================================

int main()
{
   vector<INT> F = Factorial( 100 );
   int j = F.size() - 1;   cout << F[j];
   while( --j >= 0 ) cout << setfill( '0' ) << setw( WIDTH ) << F[j];    // setfill and setw are VITAL!

   int total = 0;
   for ( j = 0; j < F.size(); j++ ) total += sumDigits( F[j] );
   cout << "\nSum of digits = " << total << '\n';
}