Preimage Size of Factorial Zeroes Function

Problem Description

Let f(x) be the number of zeroes at the end of x!. Recall that x! = 1 * 2 * 3 * ... * x and by convention, 0! = 1.

• For example, f(3) = 0 because 3! = 6 has no zeroes at the end, while f(11) = 2 because 11! = 39916800 has two zeroes at the end.

Given an integer k, return the number of non-negative integers x have the property that f(x) = k.

Example 1:

Input: k = 0
Output: 5
Explanation: 0!, 1!, 2!, 3!, and 4! end with k = 0 zeroes.

Example 2:

Input: k = 5
Output: 0
Explanation: There is no x such that x! ends in k = 5 zeroes.

Example 3:

Input: k = 3
Output: 5

Constraints:

• 0 <= k <= 109

Solution (Go)

// https://leetcode.com/problems/preimage-size-of-factorial-zeroes-function/discuss/117821/Four-binary-search-solutions-based-on-different-ideas
func preimageSizeFZF(k int) int {
	return binarySearch(k) - binarySearch(k-1)
}

func binarySearch(K int) int {
	l := 0
	r := 5 * (K + 1)

	for l <= r {
		m := l + (r-l)/2
		k := numOfTrailingZeros(m)

		if k <= K {
			l = m + 1
		} else {
			r = m - 1
		}
	}

	return r
}

func numOfTrailingZeros(x int) int {
	res := 0

	for ; x > 0; x /= 5 {
		res += x / 5
	}

	return res
}