793. Preimage Size of Factorial Zeroes Function

Problem

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 2 zeroes at the end. Given K, find how many 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.

Note:

• K will be an integer in the range [0, 10^9].

Problem Summary

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

For example, f(3) = 0, because 3! = 6 has no zeroes at the end; while f(11) = 2, because 11! = 39916800 has 2 zeroes at the end. Given K, find how many non-negative integers x have the property that f(x) = K.

Note:

• K is an integer in the range [0, 10^9].

Solution Ideas

• Given a number K, determine how many n can make the number of trailing 0s in n! equal to K.
• This problem is an enhanced inverse process based on Problem 172. Problem 172 gives n and asks for the number of trailing 0s. From Problem 172, we know that the number of trailing 0s in n! depends on the number of factors of 5. If there may be K trailing 0s, then n can be at most 5 * K. Perform binary search in the interval [0, 5* K], and determine the number of trailing 0s of mid. If K can be found, then return 5; if this K cannot be found, return 0. Why can the answer only be 0 or 5? Because after n increases by 5, the number of factors of 5 increases by one again, and the trailing zeros can increase by 1 or more (if after adding 5, there are multiple factors of 5, such as 25 or 125, then the trailing zeros may increase by multiple 0s). Therefore, the range interval of n corresponding to a valid K value is 5. Conversely, the number of n corresponding to an invalid K value is 0. K will jump at the boundary of 5^n, so some values cannot be attained. For example, when n takes values in [0,5), K = 0; when n takes values in [5,10), K = 1; when n takes values in [10,15), K = 2; when n takes values in [15,20), K = 3; when n takes values in [20,25), K = 4; when n takes values in [25,30), K = 6, because 25 provides 2 factors of 5, and thus provides 2 zeros, so K can never take the value 5. That is, when K = 5, no corresponding n can be found.
• This problem can also be solved mathematically. See Solution 2. The inspiration for this solution comes from the fact that the number of trailing 0s in n! equals the total number of factors of 5 among all numbers in [1,n]. Secondly, the result of this problem can only be 0 or 5 (see the analysis in the previous solution). With these two conclusions, we can derive it mathematically. First, n can be represented in base 5 as follows
  {{< katex display >}} n = 5^{0} * a_{0} + 5^{1} * a_{1} + 5^{2} * a_{2} + ... + 5^{n} * a_{n}, (a_{n} < 5) {{< /katex >}}
  In the formula above, the total number of factors of 5 is:
  {{< katex display >}} K = \sum_{n=0}^{n} a_{n} * c_{n} {{< /katex >}}
  This total is exactly K. For different n, the general formula for an differs, so the coefficients representing K also differ. What is the general formula for cn?
  {{< katex display >}} c_{n} = 5 * c_{n-1} + 1，c_{0} = 0 {{< /katex >}} The recurrence above can also derive a general formula (however, the general formula is not applicable for this problem; using the recurrence is more convenient): {{< katex display >}} c_{n} = \frac{5^{n} - 1 }{4} {{< /katex >}} Determining whether K can be represented in the form of these two sequences is equivalent to determining whether K can be converted into a mixed-radix number with Cn as the base. At this point, it is transformed into something similar to Problem 483. The code implementation is not difficult; see Solution 2.

Code

package leetcode

// Solution 1: Binary search
func preimageSizeFZF(K int) int {
	low, high := 0, 5*K
	for low <= high {
		mid := low + (high-low)>>1
		k := trailingZeroes(mid)
		if k == K {
			return 5
		} else if k > K {
			high = mid - 1
		} else {
			low = mid + 1
		}
	}
	return 0
}

// Solution 2: Mathematical method
func preimageSizeFZF1(K int) int {
	base := 0
	for base < K {
		base = base*5 + 1
	}
	for K > 0 {
		base = (base - 1) / 5
		if K/base == 5 {
			return 0
		}
		K %= base
	}
	return 5
}