CodeChef C_HOLIC2 Solution Find the smallest N whose factorial produces P Trailing Zeroes

Question

For CodeChef problem C_HOLIC2, I tried iterating over elements: 5, 10, 15, 20, 25,... and for each number checking the number of trailing zeros using the efficient technique as specified over here, but got TLE.

What is the fastest way to solve this using formula method?

Here is the Problem Link

Answer 1

As we know for counting the number of trailing zeros in factorial of a number, the trick used is:

The number of multiples of 5 that are less than or equal to 500 is 500÷5=100

Then, the number of multiples of 25 is 500÷25=20

Then, the number of multiples of 125 is 500÷125=4

The next power of 5 is 625, which is > than 500.

Therefore, the number of trailing zeros of is 100+20+4=124

For detailed explanation check this page

Thus, this count can be represented as:

Using this trick, given a number N you can determine the no. of trailing zeros count in its factorial. Codechef Problem Link

Now, suppose we are given the no. of trailing zeros, count and we are asked the smallest no. N whose factorial has count trailing zeros Codechef Problem Link

Here the question is how can we split count into this representation?

This is a problem because in the following examples, as we can see it becomes difficult.

The count jumps even though the no is increasing by the same amount. As you can see from the following table, count jumps at values whose factorials have integral powers of 5 as factors e.g. 25, 50, ..., 125, ...

+-------+-----+
| count | N   |
+-------+-----+
| 1     | 5   |
+-------+-----+
| 2     | 10  |
+-------+-----+
| 3     | 15  |
+-------+-----+
| 4     | 20  |
+-------+-----+
| 6     | 25  |
+-------+-----+
| 7     | 30  |
+-------+-----+
| 8     | 35  |
+-------+-----+
| 9     | 40  |
+-------+-----+
| 10    | 45  |
+-------+-----+
| 12    | 50  |
+-------+-----+
| ...   | ... |
+-------+-----+
| 28    | 120 |
+-------+-----+
| 31    | 125 |
+-------+-----+
| 32    | 130 |
+-------+-----+
| ...   | ... |
+-------+-----+

You can see this from any brute force program for this task, that these jumps occur frequently i.e. at 6, 12, 18, 24 in case of numbers whose factorials have 25.(Interval = 6=1×5+1)

After N=31 factorials will also have a factor of 125. Thus, these jumps corresponding to 25 will still occur with the same frequency i.e. at 31, 37, 43, ...

Now the next jump corresponding to 125 will be at 31+31 which is at 62. Thus jumps corresponding to 125 will occur at 31, 62, 93, 124.(Interval =31=6×5+1)

Now the jump corresponding to 625 will occur at 31×5+1=155+1=156 Thus you can see there exists a pattern. We need to find the formula for this pattern to proceed.

The series formed is 1, 6, 31, 156, ... which is 1 , 1+5 , 1+5+5² , 1+5+5²+5³ , ...

Thus, n^th term is sum of n terms of G.P. with a = 1, r = 5

Thus, the count can be something like 31+31+6+1+1, etc. We need to find this t_n which is less than count but closest to it. i.e.

Say the number is count=35, then using this we identify that t_n=31 is closest. For count=63 we again see that using this formula, we get t_n=31 to be the closest but note that here, 31 can be subtracted twice from count=63. Now we go on finding this n and keep on subtracting t_n from count till count becomes 0.

The algorithm used is:

        count=read_no()

        N=0

        while count!=0:

            n=floor(log(4*count+1,5))

            baseSum=((5**n)-1)/4

            baseOffset=(5**n)*(count/baseSum)  // This is integer division

            count=count%baseSum

            N+=baseOffset

        print(N)

Here, 5**n is 5ⁿ

Let's try working this out for an example: Say count = 70, Iteration 1:

Iteration 2:

Iteration 3:

Take another example. Say count=124 which is the one discussed at the beginning of this page: Iteration 1:

PS: All the images are completely owned by me. I had to use images because StackOverflow doesn't allow MathJax to be embedded. #StackOverflowShouldAllowMathJax