seriesfactorialzerotrailing

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


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


Solution

  • 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:

    a busy cat

    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? a busy cat

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

    a busy cat

    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+52 , 1+5+52+53 , ...

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

    a busy cat

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

    a busy cat

    Say the number is count=35, then using this we identify that tn=31 is closest. For count=63 we again see that using this formula, we get tn=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 tn 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 5n

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

    a busy cat

    Iteration 2:

    a busy cat

    Iteration 3:

    a busy cat

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

    a busy cat

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