题目

类型：二分、数学
image.png

解题思路

题目大意很重要！！
本题意思：给你一个非负整数 K，问你有多少个 n，使得 n! 结果末尾有 K 个 0。

搜索有多少个 n 满足 trailingZeroes(n) == K，其实就是在问，满足条件的 n 最小是多少，最大是多少，最大值和最小值一减，就可以算出来有多少个 n 满足条件了，其实就是 二分查找 中「搜索左侧边界」和「搜索右侧边界」这两个事儿

这道题目实际上给了限制，K 是在[0, 10^9]区间内的整数，也就是说，trailingZeroes(n) 的结果最多可以达到 10^9。
然后我们可以反推，当 trailingZeroes(n)结果为 10^9 时，n 为多少？这个不需要你精确计算出来，你只要找到一个数 hi，使得 trailingZeroes(hi)比 10^9大，就可以把 hi 当做正无穷，作为搜索区间的上界。
trailingZeroes函数是单调函数，那我们就可以猜，先算一下 trailingZeroes(INT_MAX)的结果，比10^9小一些，那再用 LONG_MAX 算一下，远超 10^9了，所以LONG_MAX可以作为搜索的上界。

代码

  1. class Solution {
  2.     public int preimageSizeFZF(int K) {
  3.         // 左边界和右边界之差 + 1 就是答案
  4.         return (int)(rightBound(K) - leftBound(K) + 1);
  5.     }
  7.     // 逻辑不变，数据类型全部改成 long
  8.     long trailingZeroes(long n) {
  9.         long res = 0;
  10.         for (long d = n; d / 5 > 0; d = d / 5) {
  11.             res += d / 5;
  12.         }
  13.         return res;
  14.     }
  16.     /* 搜索 trailingZeroes(n) == K 的左侧边界 */
  17.     long leftBound(int target) {
  18.         long lo = 0, hi = Long.MAX_VALUE;
  19.         while (lo < hi) {
  20.             long mid = lo + (hi - lo) / 2;
  21.             if (trailingZeroes(mid) < target) {
  22.                 lo = mid + 1;
  23.             } else if (trailingZeroes(mid) > target) {
  24.                 hi = mid;
  25.             } else {
  26.                 hi = mid;
  27.             }
  28.         }
  29.         return lo;
  30.     }
  32.     /* 搜索 trailingZeroes(n) == K 的右侧边界 */
  33.     long rightBound(int target) {
  34.         long lo = 0, hi = Long.MAX_VALUE;
  35.         while (lo < hi) {
  36.             long mid = lo + (hi - lo) / 2;
  37.             if (trailingZeroes(mid) < target) {
  38.                 lo = mid + 1;
  39.             } else if (trailingZeroes(mid) > target) {
  40.                 hi = mid;
  41.             } else {
  42.                 lo = mid + 1;
  43.             }
  44.         }
  46.         return lo - 1;
  47.     }
  48. }