SPOJ FCTRL

From Algorithmist
Jump to navigation Jump to search

11 - Factorial[edit]

https://www.spoj.com/problems/FCTRL/

Summary[edit]

This problem required us to determine the number of trailing zeroes for factorial n, where n is a integer between 1 and 1 billion. Obviously calculating n! itself and determining the number of trailing zeroes would result in a TLE, but if we research a bit we find a simple mathematical formula to determine Z(N):

Implementations[edit]

This is just a straightforward translation of the formula above:

int zeta(int n) {
	int ret = 0;
	for (int p = 5; p <= n; p*=5)
		ret += n/p;
	return ret;
}

Input[edit]

6
3
60
100
1024
23456
8735373

Output[edit]

0
14
24
253
5861
2183837

References[edit]

  1. Factorial - Wolfram Mathworld - [1]