Is there a way to find sum of digits of 100!?

Question

I know there is a way of finding the sum of digits of 100!(or any other big number's factorial) using Python. But I find it really tough when it comes to C++ as the the size of even LONG LONG is not enough.

I just want to know if there is some other way.

I get it that it is not possible as our processor is generally 32 bits. What I am referring is some other kind of tricky technique or algorithm which can accomplish the same using the same resources.

Answer 1

Use a digit array with the standard, on-paper method of multiplication. For example, in C :

#include <stdio.h>

#define DIGIT_COUNT 256

void multiply(int* digits, int factor) {
  int carry = 0;
  for (int i = 0; i < DIGIT_COUNT; i++) {
    int digit = digits[i];
    digit *= factor;
    digit += carry;
    digits[i] = digit % 10;
    carry = digit / 10;
  }
}

int main(int argc, char** argv) {
  int n = 100;

  int digits[DIGIT_COUNT];
  digits[0] = 1;
  for (int i = 1; i < DIGIT_COUNT; i++) { digits[i] = 0; }

  for (int i = 2; i < n; i++) { multiply(digits, i); }

  int digitSum = 0;
  for (int i = 0; i < DIGIT_COUNT; i++) { digitSum += digits[i]; }
  printf("Sum of digits in %d! is %d.\n", n, digitSum);

  return 0;
}