N! = 1*2*...N
for some i
i = 2^n*5^m* K ,
where K=i/(2^n * 5^m) is product of the rest primes constituting i other that 2 and 5.
if n>m, then 2^n*5^m = 10^m * 5^(m-n) ; else = 10^n * 5^(n-m)
We need to keep track of sum of m_i and n_i for all i from 1 to N,
as 2's and 5's (and only they ) generate min(m,n) trailing zeroes in product, and the rest 2's or 5's max(m,n)-min(m,n) is either 2^p or 5^p ( p= max(m,n)-min(m,n) )
So for each i we need m-n and last digit of K ( K_last) and for all
i from 1 to n we
accumulate sum of all (m-n)_i and product of all K_last_i
( actually we need not product as a whole but its last digit ).
Then result is ((m-n)>0 ? 5 : 2^(n-m) ) * ALL_K_last_i_product
and last digit of 2^(n-m) is simply {2,4,8,6} [ n-m mod 4 ]
and last digit of 5^n is always 5.
1
