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.
\$1\leq a,b\leq 10^6\$
First line contains \$T\$ number of test cases.
Then \$T\$ lines follow each containing 2 integers \$a\$ and \$b\$.
\$T\$ lines each containing the sum of number of zeros for the numbers in range \$[a,b]\$.
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 =  * 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 .