3
\$\begingroup\$

Ram was busy calculating the factorials of some numbers. He saw a pattern in the number of zeros in the end of the factorial. Let \$n\$ be the number and \$Z(n)\$ be the number of zeros in the end of the factorial of n then for

\$x < y\$

\$Z (x) \leq Z(y)\$

i.e. the function never decreases.

He is solving a problem and wants to calculate the sum of number of zeros in the end of factorial of numbers in the range \$[a,b]\$ i.e. sum of the number of zeros in the end for the factorial for all numbers \$n\$ such that the number \$n\leq b\$ and \$n\geq a\$. But n can be very large and he don't want to solve the problem by himself and he has asked you to solve the problem. Help him to solve the problem.

Constraints:

\$T\leq 10^5\$

\$1\leq a,b\leq 10^6\$

Input :

First line contains \$T\$ number of test cases.

Then \$T\$ lines follow each containing 2 integers \$a\$ and \$b\$.

Output:

\$T\$ lines each containing the sum of number of zeros for the numbers in range \$[a,b]\$.

My solution:

def zeros_in_factorial(n):

    if n < 5:
        return 0

    count = 0
    i = 5
    while n//i >= 1:
        count += n // i
        i *= 5
    return count

def zeros_array():
    zeros_array = [0] * 1000000
    for i in range(0,1000000,1):
        zeros_array[i]  = zeros_in_factorial(i)

    return zeros_array 

zeros = zeros_array()

i = int(raw_input())
result = []
while i > 0:
    i -= 1
    try:
        sum_0 = 0
        a, b = (raw_input().split())
        low = int(a)
        high = int(b) + 1
        for x in xrange(low,high,1):

            res = res = zeros[x]
            sum_0 += res
        result.append(sum_0)
    except (EOFError):
        break #end of file reached

for x in xrange(0,len(result)):
    print result[x].

But the problem is really large number and large range of inputs its time limit gets exceeded.

How can I improve this further .

Inputs:

  1. Input 1
  2. Input 2
  3. Input 3
  4. Input 4
  5. Input 5
  6. Input 6
\$\endgroup\$
9
\$\begingroup\$

Cool problem! Your approach is \$O(n)\$ for each pair. There are several comments I could give about your code specifically, and we could make several performance improvements based on how we generate zeros_array - but all of that will still fall into the \$O(n)\$ category. And, as you can tell, \$O(n)\$ here is too slow! Let's try to do better. Back to the drawing board.

Break it down to first principles

To start with, let's take a really simple example. Sum the number of zeros from [14,43] (just arbitrary random numbers under 100). In fact, let's simplify even further and let's pretend that 25 isn't a power of 5. So our zeros are:

S = sum([2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5,
         6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 8])
  = 159

So what do you notice about that? In terms of multiples of 5, since we're talking about a weakly increasing sequence - and a sequence that increases extremely predictably at that:

S = 2*1 + 3*5 + 4*5 + 5*5 + 6*5 + 7*5 + 8*4
S = 2*5 + 3*5 + 4*5 + 5*5 + 6*5 + 7*5 + 8*4 - 2*4
S = 5*(2+3+4+5+6+7) + (8*4 - 2*4)

I split the 8 and 2 out separately, those are the two ends and are always going to be the edge cases. You can see that 14%5 == 4 and 43%5 == 3, so those almost give us the two multiples we need. We just need to add one to the latter:

sum_to = lambda n: n*(n-1)/2
S = 5 * (sum_to(hi//5) - sum_to(lo//5)) 
  + (hi % 5 + 1) * (hi // 5) - (lo % 5) * (lo // 5)

This expression looks much more complicated than it is. Basically we're summing the "complete" parts (where we have 5 5s in a row), and then dealing with the edge cases. The key is that we have a closed form that's just a function of 5, lo, and hi. And you can see how we can easily extend this out to all the other powers of 5 that I skipped.

This solution is \$O(1)\$. There are only 8 powers of 5 worth considering, so we're doing the same number of operations across any range of numbers.

It's possible that the above expression can be simplified, but let's see where we're at before we worry about simplifying. I rewrote your code a bit to read from a file instead of raw_input for testing purposes, but the main logic is simply:

def sum_to(n):
    return n * (n-1) / 2 

def count_zeros(lo, hi):
    S = 0 
    for pow5 in (5**i for i in xrange(1,9)):
        S += pow5 * (sum_to(hi//pow5) - sum_to(lo//pow5))
        S += (hi % pow5 + 1) * (hi // pow5) - (lo % pow5) * (lo // pow5)
    return S

...

results = []
for _ in xrange(i):
    a, b = map(int, next(lines).split())
    result.append(count_zeros(a, b))
return results

Timing comparison for the first \$n\$ pairs, runtime in seconds for one single run:

          op    const
   5   2.287    0.000
  10   2.514    0.000
  25   3.392    0.000
 100   7.578    0.001
 250  14.928    0.003
1000  48.276    0.013
\$\endgroup\$
  • \$\begingroup\$ I haven't tested it on large set of input but the output results are not correct : smaller range (2,5) its giving output - 2 while correct output should be 1. large range (258731, 380182) its giving Output:- 9699214801 . but the correct result is 9699119760 \$\endgroup\$ – Ankur Anand Oct 27 '15 at 14:33
  • 1
    \$\begingroup\$ @AnkurAnand It definitely gives 1 and 969919760... \$\endgroup\$ – Barry Oct 27 '15 at 14:40
  • \$\begingroup\$ Sorry for confusion i ran wrong unit test with high + 1 .. really sorry \$\endgroup\$ – Ankur Anand Oct 27 '15 at 14:42
4
\$\begingroup\$

Barry gave a great answer with a much faster approach, but I'll point to some stuff you could improve that could be applicable in future.

You build a full list of zeros_array, but you don't need to. All you need is the total sum, yet you're creating a list of a million values. Even ints take up a lot of space at that point. Especially since you have zeros_in_factorial, you don't need your zeros_array function at all. Only store data if you need to keep it, if it's just a step to what you need then there's no reason for it to hang around. If you want to avoid redoing the same numbers, then instead think about caching results rather than building the full set in advance. This way you can avoid recalculating but still don't need to calculate values you never use.

Put simply you could just take the high and lo values, then create a loop that will add each result to a running total:

for x in xrange(low, high):
    sum_0 += zeros_in_factorial(x)

You could actually get this directly with the sum function and a generator expression. A generator expression is essentially a for loop collapsed into a single expression. They tend to be faster than using for loops, and certain functions can take them as parameters. sum can do this, so you could just used

sum_0 = sum(zeros_in_factorial(x) for x in xrange(low, high))

zeros_in_factorial is also hard to follow, and i is not a clear name. i usually denotes the index in a simple iteration going up by one at a time, but here it's being multiplied by 5 each time? Adding a docstring/some comments will make it a lot easier to follow the maths you've used to get yourself a solution here.

def zeros_in_factorial(n):
    """Calculate the number of zeroes at the end of !n"""

    # !4 and lower have no 0s at the end.
    if n < 5:
        return 0

    # divisor is INSERT EXPLANATION HERE
    count = 0
    divisor = 5
    while n // i >= 1:
        count += n // divisor
        divisor *= 5

    return count

As you can see, I don't actually know what divisor is/does. But I'm sure you can explain it for me and others.

As I said you don't need zeros_array but I'll give feedback on it anyway. When calling range you can just pass a single argument if you want a range of numbers that starts from 0 and goes up by 1 each time, as those are both defaults. In other words range(0,1000000,1) == range(1000000). You could also create it as a list comprehension, to avoid having to set all the zeroes before your real values. Also why not use xrange here? xrange is most helpful on long lists, so it makes more sense to use it here than where you did later.

[zeros_in_factorial(i) for i in xrange(1000000)]

This is a list comprehension, just like a generator expression except in this case used to create a list. Your case is pretty simple, it will iterate over the range and calculate the result for each i, creating the list the same as your original code did. In the end, this could make your function just return that list directly:

def zeros_array():
    return [zeros_in_factorial(i) for i in xrange(1000000)]

Why use while i > 0? You could just use for _ in range(i). This will iterate i times. Using _ is just a Python style way of saying that you don't care about the value, you just have to include it for the sake of the for loop.

I don't know if res = res = zeros[x] is a typo but it's the same as res = zeros[x], so it's redundant. res itself is redundant as you could just directly add zeros[x] to sum_0.

Why are you excepting an EOFError? It looks odd. When I check the docs I realise that's because empty space in the inputs will cause that. But you're not explaining that in the comment. You're just repeating what the name "End of File Error" indicates, which itself is misleading. Instead point out when this actually occurs for your use case.

\$\endgroup\$
  • 2
    \$\begingroup\$ Regarding the zeros_in_factorial(), see en.wikipedia.org/wiki/Trailing_zero. To find number of trailing zeroes you divide n first by 5, then 25, then 125, and so on, and then add these numbers together. For a 1000! you'll get: 1000 // 5 + 1000 // 25 + 1000 // 125 + 1000 // 625 = 200 + 40 + 8 + 1 = 249. There are 249 trailing zeroes for 1000! \$\endgroup\$ – holroy Oct 27 '15 at 20:38
  • \$\begingroup\$ @holroy This is a great explanation and would be a good comment. Even the wikipedia link would be helpful. \$\endgroup\$ – SuperBiasedMan Oct 27 '15 at 20:58
  • \$\begingroup\$ My comment is the explanation of OP's method. This is what is happening in his zeros_in_factorial()! \$\endgroup\$ – holroy Oct 27 '15 at 21:02
  • \$\begingroup\$ @holroy Oh I know, I'm trying to tell the OP that it's a good explanation to include as a comment. \$\endgroup\$ – SuperBiasedMan Oct 27 '15 at 21:03
  • \$\begingroup\$ Ahh... It was a little confusing... I thought I'd already had made that comment... :-) \$\endgroup\$ – holroy Oct 27 '15 at 21:04

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.