0
$\begingroup$

I need to find the number of trailing zeroes in $1^{1!} \cdot 2^{2!} \cdot 3^{3!} \cdots N^{N!}$, where $N$ is natural number.

Assuming $N$ is very large, say $500$, where you cannot find factorial of a number. Also, I need to answer by taking modulo with $100000007$.

If $N$ was small then we can simply factorise each number, and see power of $2$ and power of $5$. Whatever is small will be count of trailing zeroes. But how to solve this one ?

EXAMPLE : For $N=7$ answer is $120$, after taking modulo given prime, that is $100000007$.

How to find it for given $N$? What should be algorithm for the same. If there is direct some mathematical formula, then it would be more awesome.

Improve this question
$\endgroup$
  • $\begingroup$ If $M=2^a5^bL$ where $L$ isn't a multiple of $2$ or $5$, then the number of trailing zeros in $M$ is just $\min\{a,b\}$. So to find a formula, you should start by counting how many times $2$ and $5$ divide your large number. $\endgroup$ – Greg Martin Mar 12 '16 at 18:42
  • $\begingroup$ @GregMartin But what about power of the M here. Its factorial of a very large number. How to deal with it $\endgroup$ – mat7 Mar 12 '16 at 18:45
  • $\begingroup$ There are ways of finding a huge number (mod $p$) without ever finding the huge number. Basically, every time you multiply, reduce the answer (mod $p$) before multiplying further. Hopefully you know about modular exponentiation (if not, I recommend learning about it); the idea for factorials is similar. $\endgroup$ – Greg Martin Mar 12 '16 at 18:47
  • $\begingroup$ Unless I'm missing something, the answer for $N=7$ is $0$ because $7^{7!}$ is a power of $7$, hence cannot divide evenly into $10$. $\endgroup$ – Justin Benfield Mar 12 '16 at 19:17
  • $\begingroup$ @JustinBenfield: There are still factors of $5^{5!}$ and $2^{2!+2\cdot 4!+6!}$. $\endgroup$ – hmakholm left over Monica Mar 12 '16 at 19:24
0
$\begingroup$

I am just showing you an algorithm. I thought of it. 

twos = 0
fives = 0

For n in numbers from 1 to n:

    a = (number mod 2 == 0)
    b = (number mod 5 == 0)

    if a or b:
        k = factorial(n)

        if a == True:
            twos = twos + (number of times 2 can be divided from n)*k

        if b == True:
            fives = fives + (number of times 5 can be divided from n)*k


print(min(twos, fives) mod 100000007)

It fits with the test case you gave of n = 7. I advise you not to use a recursive implementation of factorial. One of dynamic programming or a for loop would do.

Explanation: This algorithm finds out the number of 2's and 5's in the numbers prime factorisation. You might find the '(number of times 2 can be divided from n)*k' strange but this is actually due to the fact that some numbers like 4, 10 & 25 have many 2's and 5's in their factorisation. If you are wondering about a and b then just imagine that there are some numbers which aren't divisible by 2 or 5 and finding their factorial would be a total waste of time and may increase the time expense. The simple 'or' is a binary logic gate. a and b are Booleans.

I wrote simple code to find the solution to your problem without using my algorithm and it stuck at 10. You will have to employ this algorithm to be able to find the answer.

Hope you found that useful.

Improve this answer
$\endgroup$
  • $\begingroup$ Calculating factorial of 500 is not computable in a computer :(. Unless we take modulo. $\endgroup$ – mat7 Mar 13 '16 at 17:49
  • $\begingroup$ @mat7 Check my answer and say if you have some doubts. $\endgroup$ – TheRandomGuy Mar 14 '16 at 8:06
  • $\begingroup$ @mat7 This should be the algorithm to implement. It reduces the time consumption. Taking factorials upto 1000 doesn't require much time and unless you are calculating it for real large numbers, the method is considerable. $\endgroup$ – TheRandomGuy Mar 14 '16 at 8:45
  • $\begingroup$ @mat7 Many programming languages, Java for example, provide big integer arithmetic. The factorial of 500 is computed instantly, but is too long for this comment! $\endgroup$ – Thumbnail Apr 6 '17 at 9:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.