[Java] Number of trailing zeroes in factorial

Given a number N, return the amount of trailing zeroes in its factorial.

Example:

4! = 24, no trailing zeroes

10! = 3628800, two trailing zeroes

100! = something big with 24 trailing zeroes

We could compute the factorial then count the zeroes, which is O(N) time and might work for small values of N, however multiplication can be indeed expensive.

After writing down some examples we can notice the better approach in solving this problem:

4! = 4 * 3 * 2 * 1

10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1

To have a trailing zero as a result of multiplication we MUST have multiplied a 5 with a 2, no other combination would result in that.

The amount of trailing zeroes would then be dictated exactly by the number of 5,2 pairs present in the multiplication chain:

4! = 4(2^2) * 3 * 2(2^1)

there are three available 2s, but no 5s, so no zeroes can be in output.

10! = 10(5*2) * 9 * 8(2^3) * 7 * 6(3*2) * 5(5*1) * 4(2^2) * 3 * 2(2^1)

there are eight available 2s and two 5s, therefore only two 5,2 pairs, for a total of two zeroes in output.

Since 5 is bigger than 2, for each 5 there will be for sure a 2 to complete the pair, we can simply count the amount of 5s appearing in the chain to determine our result.

We can either generate a power of 5, divide our N by it, track the partial count, continue until N can be divided by the current power of 5 or we can simply keep dividing our N by 5 until N is exactly 5 tracking the result of the division as partial count each time.

This will result in a O(log(N)) algorithm (log5(N) precisely) since we divide our input by 5 at each iteration.

Either way is using constant space.

You can check my implementation of factorialTrailingZeroes on my Gist along with some tests in FactorialTrailingZeroesJTests.