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

Question

Hey guys , 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. EDIT: i just want to know if there is some other way , i am not aware of which can do the needful. thanks

see guys 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

If you're referring to the Project Euler problem, my reading of that is that it wants you to write your own arbitrary-precision integer library or class that can multiply numbers.

My suggestion is to store the base-10 digits of a number, in reverse order to the way you'd normally write them, because you'll need to convert the number to base 10 in the end, anyway. Storing the digits in reverse order makes writing the addition and multiplication routines slightly easier, in my opinion. Then write addition and multiplication routines that emulate how you would add or multiply numbers manually.

Answer 2

Anything bigger than 32-bit integer multiplication can not be done natively by the processor without some assistance. This could be rather tricky and may even require some assembly programming. Nonetheless, it is very much possible with some thought.

Answer 3

There are a number of BigInteger libraries available in C++. Just Google "C++ BigInteger". But if this is a programming contest problem then you should better try to implement your own BigInteger library.

Answer 4

How are you going to find the sum of digits of 100!. If you calculate 100! first, and then find the sum, then what is the point. You will have to use some intelligent logic to find it without actually calculating 100!. Remove all the factors of five because they are only going to add zeros. Think in this direction rather than thinking about the big number. Also I am sure the final answer i.e. the sum of the digits will be within LONG LONG.

There are C++ big int libraries, but I think the emphasis here is on algorithm rather than library.

Answer 5

long long is not a part of C++. g++ provides it as an extension.

Arbitrary Precision Arithmetic is something that you are looking for. Check out the pseudocode given in the wiki page.

Furthermore long long cannot store such large values. So you can either create your BigInteger Class or you can use some 3rd party libraries like GMP or C++ BigInteger.

Answer 6

You could take the easy road and use perl/python/lisp/scheme/erlang/etc to calculate 100! using one of their built-in bignum libraries or the fact some languages use exact integer arithmetic. Then take that number, store it into a string, and find the sum of the characters (accounting for '0' = 48 etc).

Or, you could consider that in 100!, you will get a really large number with many many zeros. If you calculate 100! iteratively, consider dividing by 10 every time the current factorial is divisible by 10. I believe this will yield a result within the range of long long or something.

Or, probably a better exercise is to write your own big int library. You will need it for some later problems if you do not determine the clever tricks.

Answer 7

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;
}

Answer 8

Observe that multiplying any number by 10 or 100 does not change the sum of the digits.

Once you recognize that, see that multiplying by 2 and 5, or by 20 and 50, also does not change the sum, since 2x5 = 10 and 20x50 = 1000.

Then notice that anytime your current computation ends in a 0, you can simply divide by 10, and keep calculating your factorial.

Make a few more observations about shortcuts to eliminate numbers from 1 to 100, and I think you might be able to fit the answer into standard ints.

Answer 9

Nothing in project Euler requires more than __int64.

I would suggest trying to do it using base 10000.