conorgriffin conorgriffin - 28 days ago 25
C++ Question

Calculating large factorials in C++

I understand this is a classic programming problem and therefore I want to be clear I'm not looking for code as a solution, but would appreciate a push in the right direction. I'm learning C++ and as part of the learning process I'm attempting some programming problems. I'm attempting to write a program which deals with numbers up to factorial of 1billion. Obviously these are going to be enormous numbers and way too big to be dealing with using normal arithmetic operations. Any indication as to what direction I should go in trying to solve this type of problem would be appreciated.

I'd rather try to solve this without using additional libraries if possible

Thanks

PS - the problem is here http://www.codechef.com/problems/FCTRL




Here's the method I used to solve the problem, this was achieved by reading the comments below:

Solution -- The number 5 is a prime factor of any number ending in zero. Therefore, dividing the factorial number by 5, recursively, and adding the quotients, you get the number of trailing zeros in the factorial result

E.G. - Number of trailing zeros in 126! = 31

126/5 = 25 remainder 1

25/5 = 5 remainder 0

5/5 = 1 remainder 0

25 + 5 + 1 = 31

This works for any value, just keep dividing until the quotient is less
than 5

Answer Source

Skimmed this question, not sure if I really got it right but here's a deductive guess:

First question - how do you get a zero on the end of the number? By multiplying by 10.

How do you multiply by 10? either by multiplying by either a 10 or by 2 x 5...

So, for X! how many 10s and 2x5s do you have...?

(luckily 2 & 5 are prime numbers)

edit: Here's another hint - I don't think you need to do any multiplication. Let me know if you need another hint.