LeetCode 793 - Preimage Size of Factorial Zeroes Function

Related:
LeetCode 175 - Factorial Trailing Zeroes
LeetCode 793 - Preimage Size of Factorial Zeroes Function
https://leetcode.com/problems/preimage-size-of-factorial-zeroes-function/

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]

http://bookshadow.com/weblog/2018/03/04/leetcode-preimage-size-of-factorial-zeroes-function/

n!后缀0的个数K，等于不大于n的所有乘数中，因子5的个数。

计算公式为：K = (n / 5) + (n / 25) + (n / 125) + ... + n / (5^k)

由等比数列前N项和公式得不等式：K <= n / 4

n从4 * K开始递增枚举 + 验证即可

https://blog.csdn.net/Faldict/article/details/79451711
To begin with, we can infer that the result is either 0 or 5. We just need to judge if the input K is valid, which depends on how many 5 in x!. In convenience, we transform x into x / 5 and find the proper x such that f(x) = k.

Calculating the original x from K inversely seems not easy. However, we can write up the formula to calculate K from a given x. Here is the formula and the algorithm:

Formula:

k = x + x / 5 + x / 25 + x / 125 + ...
1
Algorithm:

f(x) =
    k <- x
    while x / 5 > 0
        x <- x / 5
        k <- k + x
    return k
Then we can estimate the range of x, which is smaller than K and larger than 4K/5. So we just need to iterate from 4K/5 to K and find the right x to check whether the K is valid. However, the time cost is a little expensive, so we should use binary search to speed up. Finally, we can write the full code as below.

https://blog.csdn.net/magicbean2/article/details/79754592
通过数学知识我们可以知道，f(x)后面有多少个零，取决于在[1, x]区间内的所有数中，一共有多少个5的因数（5， 10各算一个，25算有两个5的因数，125算3个，以此类推）。而我们发现，f(x)其实是单调的阶跃函数，如下图所示：



所以给定一个K，我们需要做的就是在横坐标上找到对应的X区间。可以发现，如果K落在上图所示的水平区域内，那么满足f(x) = K的x的个数就是5；否则就是0，例如上图所示的K从4到6的跳跃，对应于x从24到25。这样我们就可以采用二分查找的方法，确定x究竟处在哪个区域，从而判断满足f(x) = K的个数到底是5还是0。

  int preimageSizeFZF(int K) {

    long left = 0, right = 5L * (K + 1);

    while (left <= right) {

      long mid = left + (right - left) / 2;

      long num = numOfTrailingZeros(mid);

      if (num < K) {

        left = mid + 1;

      } else if (num > K) {

        right = mid - 1;

      } else {

        return 5;

      }

    }

    return 0;

  }

  long numOfTrailingZeros(long x) {

    long res = 0;

    for (; x > 0; x /= 5) {

      res += x / 5;

    }

    return res;

  }

http://www.cnblogs.com/grandyang/p/9214055.html

这道题的题目名称非常的难懂，但是读了题目内容以后，就不难理解了，定义函数f(x)为x!的末尾0的个数，现在给了我们一个非负整数K，问使得f(x)=K成立的非负整数的个数。我们之前做过一道有关阶乘末尾零的个数的题Factorial Trailing Zeroes，从那道里我们知道了末尾0其实是由2和5相乘为10得到的，而阶乘中2的数量远多于5的个数，所以10的个数就只取决于5的个数。需要注意的一点就是，像25，125，这样的不只含有一个5的数字需要考虑进去。比如，24的阶乘末尾有4个0，分别是5，10，15，20中的四个5组成的，而25的阶乘末尾就有6个0，分别是5，10，15，20中的各一个5，还有25中的两个5，所以共有六个5，那么就不存在其阶乘数末尾有5个0的数。还有一个很重要的规律需要发现，我们知道20，21，22，23，24，这五个数的阶乘数末尾零的个数其实是相同的，都是有4个，因为它们包含的5的个数相同。而19，18，17，16，15，这五个数末尾零个数相同，均为3。那么我们其实可以发现，每五个数，必会至少多出1个5，有可能更多。所以阶乘末尾零个数均为K个的x值，只有两种情况，要么是5，要么是0，这个规律得出来后，我们继续向着正确的解题方向前进。

基于之前那道题Factorial Trailing Zeroes的解法，我们知道了如何快速求一个给定的数字阶乘末尾零的个数，那么我们只要找到了一个这样的数，其阶乘末尾零的个数等于K的话，那么就说明总共有5个这样的数，返回5，反之，如果找不到这样的数字，就返回0。那么像这种选一个candidate数字，再进行验证的操作，用二分搜索法就是极好的，属于博主的总结帖中LeetCode Binary Search Summary 二分搜索法小结的第四类，用子函数当作判断关系。我们首先要确定二分搜索法的范围，左边界很好确定，为0就行了，关键是来确定右边界，我们来分析一下，一个数字的阶乘末尾零个数为K，那么这个数字能有多大，就拿前面举的例子来说吧，末尾有4个0的最大数字是24，有六个0的最大是29，那么我们发现它们都不会超过5*(K+1)这个范围，所以这就是我们的右边界，注意右边界可能会超过整型数范围，所以要用长整型来表示。那么之后就是经典的二分搜索法的步骤了，确定一个中间值mid，然后调用子函数来计算mid的阶乘数末尾零的个数，用来和K比较大小，如果想等了，直接返回5，如果小于K，那么更新left为mid+1，反之，更新right为mid即可，最终没找到的话，返回0即可

https://leetcode.com/problems/preimage-size-of-factorial-zeroes-function/discuss/117619/Using-Binary-Search-Java-Solution

Given N - No. of zeroes in N! can be found by N/5, N/25, N/125 so on 
So Here use Binary search, from 0 to 10^9 - take mid element and check for No. of Zeroes

Find lower range and Higher Range : in between that is the numbers 

Lower Range : Strictly <K zeroes - 
Higher Range : Strictly >=K zeroes


No. of zeroes Range once it starts - it will never decrease
 Example 
 0! - 4! - 0 zeroes 
5! - 9! - 1 zero
10! onwards 2 zeroes, so on




    public int preimageSizeFZF(int K) {
       
        /*
        findRange(K)- All elements factorial <= Kzeroes
        
        findRange(K-1) -All elements factorial <= K-1 zeroes
        
        */
        return findRange(K)-findRange(K-1);   
    }

https://leetcode.com/problems/preimage-size-of-factorial-zeroes-function/discuss/117821/Four-binary-search-solutions-based-on-different-ideas

1. The number of trailing zeros of the factorial x! is given by the minimum of num_2 and num_5, where the former is the total number of factor 2 of integers in the range [1, x], while the latter is the total number of factor 5 of these integers. Since we always have more factors of 2 than 5, the number of trailing zeros of x! will always be num_5.
2. num_5 of x! can be computed by summing up the count of integers in the range [1, x] that are integer multiples of 5, 25, 125, ..., 5^k, ..., etc. A simple implementation is as follows:

   private long numOfTrailingZeros(long x) {
       long res = 0;
     
       for (; x > 0; x /= 5) {
           res += x/5;
       }
     
       return res;
   }
   

3. Given two non-negative integers x and y, if x <= y, then numOfTrailingZeros(x) <= numOfTrailingZeros(y), which implies numOfTrailingZeros is a non-decreasing function of x.

Our first binary solution is based on the third observation where we search the range of integers such that the numOfTrailingZeros function is evaluated to K, as shown below.

Binary search solution ONE -- search for x range:

This solution takes advantage of the last observation mentioned above, where we use binary search to find the largest integers x and y such that numOfTrailingZeros(x) <= K and numOfTrailingZeros(y) <= K-1, respectively. Then the factorial of all integers in the range (y, x] (left exclusive, right inclusive) will have K trailing zeros. Therefore the total number of non-negative integers whose factorials have K trailing zeros will be given by x - y.

The following is the Java code for this solution, where the time complexity is O((logK)^2) and space complexity is O(1). Note that x! will always have at least x/5 trailing zeros, therefore, if x is the largest integer such that x! has no more than K trailing zeros, then we have x <= 5 * (K + 1), which can serve as the upper bound of our binary search.

public int preimageSizeFZF(int K) {
    return (int)(binarySearch(K) - binarySearch(K - 1));
}
    
private long binarySearch(int K) {
    long l = 0, r =  5L * (K + 1);
    
    while (l <= r) {
        long m = l + (r - l) / 2;
        long k = numOfTrailingZeros(m);
        
        if (k <= K) {
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    
    return r;
}

---

More advanced observations:

1. Let K = numOfTrailingZeros(x), then K will jump whenever x is an integer multiple of 5 (this is a direct result of the fact that the number of factor 5 in x! will change whenever x is an integer multiple of 5). The step of the jump will be given by the number of factor 5 in x (no factorial). For example, K will jump by 1 step at x = 5, 10, 15, 20, but by 2 steps at 25, as demonstrated in the following plot:
   
2. Since the steps of the jump may be greater than 1, not all integer values can be taken by K. For example, K cannot be 5 as the step at x = 25 is two so K will jump from 4 directly to 6, thus skip the middle value of 5 (see the red dashed line between two brown lines in the above plot). We shall call these skipped integers as invalid values for K and conclude there are NO integers x such that x! has K trailing zeros at these K values. Furthermore, for each valid K value, there will be exactly FIVEintegers x such that x! has K trailing zeros (this is because if x is an integer multiple of 5, then x+1, x+2, x+3, x+4 will have no factor of 5, thus the jump step at each of these points will be 0, which implies K will remain the same in the range [x, x+4]). In summary, we conclude the number of integers x such that x! has Ktrailing zeros will be either 0 or 5, where the former corresponds to invalid K values while the latter corresponds to valid K values.
3. As a direct result of the above observation, all the valid K values will form an ordered list of ranges where each range consists of 5 continuous integers, i.e., the valid Kvalues are: [0, 5), [6, 11), [12, 17), ..., etc. The K values will break up whenever x is an integer multiple of 25 and the size (i.e., number of elements) of the gap between the two separated ranges will be given by the number of factor 5 in x minus 1 (note it's the number of factor minus 1, not x, and is equivalent to the number of factor 5 in x/5).

The following three solutions are all based on the fact that the number of integers x such that x! has K trailing zeros will be 0 when the given K value is invalid, and wil be 5 if the given K value is valid. So all we need to do is to determine whether the given K value is valid or not.

Solution TWO takes advantage of the fact that if the given K value is valid, then there must exist at least one integer x such that x! has K trailing zeros.

Solution THREE takes advantage of the third observation above and tries to find the largest valid range with a start point no more than the given K.

Solution FOUR takes advantage of the recursive structure of the invalid K values and tries to verify directly if the given K value falls into this structure.

---

Binary search solution TWO -- search for x value:

This solution makes use of the aforementioned observation that the total number of non-negative integers x such that x! has K trailing zeros will be either 0 or 5. So we can directly try binary search to find one such integer. If it exists, the K value is valid so we return 5; otherwise we return 0. The time and space complexities are the same as the first solution above, except now we only need to do the binary search once instead of twice.

public int preimageSizeFZF(int K) {
    for (long l = 0, r =  5L * (K + 1); l <= r;) {
        long m = l + (r - l) / 2;
        long k = numOfTrailingZeros(m);
        
        if (k < K) {
            l = m + 1;
        } else if (k > K) {
            r = m - 1;
        } else {
            return 5;
        }
    }
    
    return 0;
}

---

Binary search solution THREE -- search for valid K values:

As mentioned above, the valid K values will form an ordered list of ranges separated by gaps. We can order them as follows:

index:      0        1           2      ...       m
range:    [0, 5)   [6, 11)    [12, 17)  ...  [T_m, T_m + 5)
gaps:  {}       {5}       {11}          ... 

If we take all valid ranges and gaps before index m, we know those values will fill up the range [0, T_m), in which there are m * 5 valid values (we have m valid ranges and each range contains 5 elements), and sum(gap_i) invalid values (where gap_i is the number of elements in the i-th gap with 0 <= i <= m, and we define that the i-thgap is immediately preceding the i-th range). So we obtain:

T_m = m * 5 + sum(gap_i)

Now to compute T_m, we need to evalutae sum(gap_i). To evalutae sum(gap_i), we need to refer to its definition: the number of elements in the i-th gap. We know that a gap is generated whenever x is an integer multiple of 25 and the number of elements in the gap is given by the number of factor 5 in x/5. Therefore the i-th gap corresponds to x_i = i * 25, and sum(gap_i) is equivalent to the total sum of factor 5 of integers in the range [1, 5*m], which by definition is given by numOfTrailingZeros(m * 5). So we arrive at:

T_m = m * 5 + numOfTrailingZeros(m * 5)

For the given K, we can do a binary search to find the largest index m such that T_m <= K, then K will be valid if and only if it falls within the m-th range. The following is the code for this solution, with time and space complexities the same as the first solution.

public int preimageSizeFZF(int K) {
    long l = 0, r = K/5;
        
    while (l <= r) {
        long m = l + (r - l) / 2;
        long k = m * 5 + numOfTrailingZeros(m * 5);
            
        if (k <= K) {
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
  
    return (K < r * 5 + numOfTrailingZeros(r * 5) + 5 ? 5 : 0);
}

---

Binary search solution FOUR -- search for invalid K values:

In constrast to the previous solution, this solution tries to directly identify the set containing all the invalid K values and check if the given K value falls into this invalid set. To build the invalid set, we will divide the x values into ranges of the form (0, 5^m] and find the skipped values in the corresponding K ranges (recall that the skipping will happen whenever x is an integer multiple of 25), for example,

1. m = 1: the corresponding K range is [0, 1] and no values in this range are skipped, so the invalid set is empty. We will denote it as S1 = {} with length f1 = 0.
2. m = 2: the corresponding K range is [0, 6] and we do have one value that is skipped, which is 5. So the invalid set will be S2 = {5} with length f2 = 1.
3. m = 3: the corresponding K range is [0, 31] and we have multiple values that are skipped. In this case, the invalid set will be S3 = {5, 11, 17, 23, 29, 30} with length f3 = 6.
4. ... and so on

Note that the invalid set of K values for the x range (0, 5^m] can be constructed from that of (0, 5^(m-1)]. This is because (0, 5^m] can be subdivided into five smaller ranges:

(0, 5^(m-1)]
(5^(m-1), 2 * 5^(m-1)]
(2 * 5^(m-1), 3 * 5^(m-1)]
(3 * 5^(m-1), 4 * 5^(m-1)]
(4 * 5^(m-1), 5 * 5^(m-1)]

All these subranges will contain the same number of skipped K values except for the last one, which produces one additional invalid K value due to an extra factor of 5 at x = 5^m. Let's take m = 3 as an example, where the x range is (0, 125]. The five subranges are (0, 25], (25, 50], (50, 75], (75, 100], (100, 125]. There will be one K value skipped for each of the first four ranges: (0, 25], (25, 50], (50, 75], (75, 100], and two K values skipped for the last range (100, 125] due to the extra factor of 5 at x = 125 (compared to x = 25).

So in general we have f_m = 5 * f_(m-1) + 1. Now to construct S_m from S_(m-1), we have to find the values skipped in each of the last four subranges. Note that they are not just copies of S_(m-1), but instead, will be S_(m-1) shifted by some value (that is, a new set obtained by shifting the elements in S_(m-1)). The shifting value will be an integer multiple of f_m, so that we have:

Subranges:                          Skipped values
(0, 5^(m-1)]                        S_(m-1)
(5^(m-1), 2 * 5^(m-1)]              S_(m-1) + f_m
(2 * 5^(m-1), 3 * 5^(m-1)]          S_(m-1) + 2 * f_m
(3 * 5^(m-1), 4 * 5^(m-1)]          S_(m-1) + 3 * f_m
(4 * 5^(m-1), 5 * 5^(m-1)]          S_(m-1) + 4 * f_m

Therefore, S_m can be written in terms of S_(m-1) as:

S_m = {S_(m-1)} U {S_(m-1) + f_m} U {S_(m-1) + 2 * f_m} U {S_(m-1) + 3 * f_m} U {S_(m-1) + 4 * f_m} U {5*f_m}.

where U means union operation and the last single element 5 * f_m is due to the extra factor of 5 at x = 5^m.

Okay, we have obtained the recurrence relations for S_m, but apparently we cannot afford to compute its elements explicitly (which requires exponential space and time). So how do we check if the given K value is in S_m or not?

Our strategy is simple: first check if K is the single element 5 * f_m. If not, we will take the modulo with respect to f_m and recursively check to see if the remainder is in S_(m-1). We can do this because if an element is in the set S_(m-1) + k * f_m, then the remainder of the element with respect to f_m will be in the set S_(m-1).

So finally, here is the code for this solution. Note that the given K value does not exceed 10^9 so it makes no sense to test S_m with size greater than that, hence we start with the one with size right below 10^9, which happens to be 305175781. The time complexity is then given by O(logK) and space complexity O(1).

public int preimageSizeFZF(int K) {
    for (int f = 305175781; f >= 1; f = (f - 1) / 5) {
        if (K == 5 * f) return 0;
        K %= f;
    }
    
    return 5;
}

X.

下面这种解法也挺巧妙的，也是根据观察规律推出来的，我们首先来x为1到25的情况：

x:    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
f(x): 0 0 0 0 1 1 1 1 1 2  2  2  2  2  3  3  3  3  3  4  4  4  4  4  6
g(x): 0 0 0 0 1 0 0 0 0 1  0  0  0  0  1  0  0  0  0  1  0  0  0  0  2

这里，f(x)是表示x!末尾零的个数，而g(x) = f(x) - f(x-1)，那么我们其实还可以通过观察发现，f(x) = sum(g(x)).

我们再仔细观察上面的数字，发现g(x)有正值的时候都是当x是5的倍数的时候，那么我们来专门看一下x是5的倍数时的情况吧：

x:    5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100 105 110 115 120 125
g(x): 1 1  1  1  2  1  1  1  1  2  1  1  1  1  2  1  1  1  1   2   1   1   1   1   3

仔细观察上面的红色数字，g(x)=1时，是5的倍数，g(x)=2时，都是25的倍数，g(x)=3时，是125的倍数，那么我们就有：

g(x) = 0     if x % 5 != 0,
g(x) >= 1    if x % 5 == 0,
g(x) >= 2   if x % 25 == 0.

如果我们继续将上面的数字写下去，我们可以发现规律，g(x)按照 1 1 1 1 x 的规律重复五次，第五次的时候x自增1。我们再继续观察:

当x=25时，g(x)=2，此时K=5被跳过了。

当x=50时，g(x)=2，此时K=11被跳过了。

当x=75时，g(x)=2，此时K=17被跳过了。

当x=100时，g(x)=2，此时K=23被跳过了。

当x=125时，g(x)=3，此时K=29，30被跳过了。

进一步，我们可以发现如下规律：

5(=1*5), 11(=6*1+5), 17(=6*2+5), 23(=6*3+5), 29(=6*4+5), 30(=6*5), 36(=31+5), 42(=31+6+5), 48(=31+6*2+5)

这些使得x不存在的K，出现都是有规律的，它们减去一个特定的基数base后，都是余5，而余1，2，3，4的，都是返回5。那么这个基数base，实际是1，6，31，156，...，是由 base = base * 5 + 1，不断构成的，通过这种不断对基数取余的操作，我们可以最终将K降为小于等于5的数，就可以直接返回结果了

    int preimageSizeFZF(int K) {
        if (K < 5) return 5;
        int base = 1;
        while (base * 5 + 1 <= K) {
            base = base * 5 + 1;
        }
        if (K / base == 5) return 0;
        return preimageSizeFZF(K % base);
    }