Zeros in Factorial

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 def zeros_in_factorial(n):

if n = 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:

• Input 1

• Input 2

• Input 3

• Input 4

• Input 5

• Input 6

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

StackExchange Code Review Q#108874, answer score: 9