迭代（整除 / 相除 2 解法），二分查找，传递函数，求解《172. 阶乘后的零》和《793. 阶乘函数后 K 个零》
例题
172. 阶乘后的零
给定一个整数 n ，返回 n! 结果中尾随零的数量。
提示 n! = n (n - 1) (n - 2) ... 3 2 1
示例 1：
输入：n = 3
输出：0
解释：3! = 6 ，不含尾随 0
示例 2：
输入：n = 5
输出：1
解释：5! = 120 ，有一个尾随 0
示例 3：
输入：n = 0
输出：0
提示：
0 <= n <= 104
进阶：你可以设计并实现对数时间复杂度的算法来解决此问题吗？
答案
迭代 · 整除
var trailingZeroes = function(n) {
let r = 0
while (n >= 5) {
n /= 5
n |= 0
r += n
}
return r
};function trailingZeroes(n: number): number {
let r = 0
while (n >= 5) {
n = Math.floor(n / 5)
r += n
}
return r
};class Solution {
function trailingZeroes($n) {
$r = 0;
while ($n >= 5) {
$n /= 5;
$n |= 0;
$r += $n;
}
return $r;
}
}func trailingZeroes(n int) int {
r := 0
for n >= 5 {
n /= 5
r += n
}
return r
}class Solution {
public int trailingZeroes(int n) {
int r = 0;
while (n >= 5) {
n /= 5;
r += n;
}
return r;
}
}public class Solution {
public int TrailingZeroes(int n) {
int r = 0;
while (n >= 5) {
n /= 5;
r += n;
}
return r;
}
}int trailingZeroes(int n){
int r = 0;
while (n >= 5) {
n /= 5;
r += n;
}
return r;
}class Solution {
public:
int trailingZeroes(int n) {
int r = 0;
while (n >= 5) {
n /= 5;
r += n;
}
return r;
}
};class Solution: # // 整除
def trailingZeroes(self, n: int) -> int:
r = 0
while n >= 5:
n //= 5
r += n
return r迭代 · 乘法
var trailingZeroes = function(n) {
let r = 0, divisor = 5
while (divisor <= n) {
r += n / divisor | 0
divisor *= 5
}
return r
};function trailingZeroes(n: number): number {
let r = 0, divisor = 5
while (divisor <= n) {
r += n / divisor | 0
divisor *= 5
}
return r
};class Solution {
function trailingZeroes($n) {
$r = 0;
$divisor = 5;
while ($divisor <= $n) {
$r += $n / $divisor | 0;
$divisor *= 5;
}
return $r;
}
}func trailingZeroes(n int) int {
r, divisor := 0, 5
for divisor <= n {
r += n / divisor
divisor *= 5
}
return r
}class Solution {
public int trailingZeroes(int n) {
int r = 0, divisor = 5;
while (divisor <= n) {
r += n / divisor;
divisor *= 5;
}
return r;
}
}public class Solution {
public int TrailingZeroes(int n) {
int r = 0, divisor = 5;
while (divisor <= n) {
r += n / divisor;
divisor *= 5;
}
return r;
}
}int trailingZeroes(int n){
int r = 0, divisor = 5;
while (divisor <= n) {
r += n / divisor;
divisor *= 5;
}
return r;
}class Solution {
public:
int trailingZeroes(int n) {
int r = 0, divisor = 5;
while (divisor <= n) {
r += n / divisor;
divisor *= 5;
}
return r;
}
};class Solution:
def trailingZeroes(self, n: int) -> int:
r, divisor = 0, 5
while divisor <= n:
r += n // divisor
divisor *= 5
return r793. 阶乘函数后 K 个零
f(x) 是 x! 末尾是 0 的数量。回想一下 x! = 1 2 3 ... x，且 0! = 1 。
例如， f(3) = 0 ，因为 3! = 6 的末尾没有 0 ；而 f(11) = 2 ，因为 11!= 39916800 末端有 2 个 0 。
给定 k，找出返回能满足 f(x) = k 的非负整数 x 的数量。
示例 1：
输入：k = 0
输出：5
解释：0!, 1!, 2!, 3!, 和 4! 均符合 k = 0 的条件。
示例 2：
输入：k = 5
输出：0
解释：没有匹配到这样的 x!，符合 k = 5 的条件。
示例 3:
输入: k = 3
输出: 5
提示:
0 <= k <= 109
答案
二分查找
var preimageSizeFZF = function(k) {
return k < 5 || trailingZeroes(binarySearch(4 * k, 5 * k, m => trailingZeroes(m) >= k)) === k ? 5 : 0
};
const trailingZeroes = n => {
let r = 0
while (n >= 5) {
n /= 5
n |= 0
r += n
}
return r
}
const binarySearch = (l, r, cb) => {
while (l < r) {
const m = Math.floor((l + r) / 2)
if (cb(m)) r = m
else l = m + 1
}
return l
}function preimageSizeFZF(k: number): number {
return k < 5 || trailingZeroes(lower_bound(4 * k, 5 * k, m => trailingZeroes(m) >= k)) === k ? 5 : 0
};
const trailingZeroes = (n: number): number => {
let r = 0, divisor = 5
while (divisor <= n) {
r += n / divisor | 0
divisor *= 5
}
return r
}
const lower_bound = (l: number, r: number, cb: (number) => boolean): number => {
while (l <= r) {
const m = Math.floor((l + r) / 2)
if (cb(m)) r = m - 1
else l = m + 1
}
return l
}class Solution {
function preimageSizeFZF($k) {
return ($k < 5 || $this->trailingZeroes($this->binarySearch(4 * $k, 5 * $k, function($m) use($k) {
return $this->trailingZeroes($m) >= $k;
})) === $k) ? 5 : 0;
}
function trailingZeroes($n) {
$r = 0;
$divisor = 5;
while ($divisor <= $n) {
$r += $n / $divisor | 0;
$divisor *= 5;
}
return $r;
}
function binarySearch($l, $r, $cb) {
while ($l < $r) {
$m = floor(($l + $r) / 2);
if ($cb($m)) $r = $m;
else $l = $m + 1;
}
return $l;
}
}func preimageSizeFZF(k int) int {
if k < 5 || trailingZeroes(sort.Search(5 * k, func(m int) bool {
return trailingZeroes(m) >= k
})) == k {
return 5
}
return 0
}
func trailingZeroes(n int) int {
r := 0
for n >= 5 {
n /= 5
r += n
}
return r
}class Solution {
public int preimageSizeFZF(int k) { // 注意 4L 和 5L 类型转换
return k < 5 || trailingZeroes(binarySearch(4L * k, 5L * k, (m) -> trailingZeroes(m) >= k)) == k ? 5 : 0;
}
public int trailingZeroes(long n) {
int r = 0;
while (n >= 5) {
n /= 5;
r += n;
}
return r;
}
public long binarySearch(long l, long r, Function<Long, Boolean> cb) {
while (l < r) {
long m = (l + r) / 2;
if (cb.apply(m)) r = m;
else l = m + 1;
}
return l;
}
}public class Solution {
public int PreimageSizeFZF(int k) {
return k < 5 || trailingZeroes(lower_bound(4L * k, 5L * k, (m) => trailingZeroes(m) >= k)) == k ? 5 : 0;
}
private long trailingZeroes(long n) {
long r = 0, divisor = 5;
while (divisor <= n) {
r += n / divisor;
divisor *= 5;
}
return r;
}
private long lower_bound(long l, long r, Func<long, bool> cb) {
while (l <= r) {
long m = (l + r) / 2;
if (cb(m)) r = m - 1;
else l = m + 1;
}
return l;
}
}class Solution {
public:
int preimageSizeFZF(int k) { // 回调函数注意 capture this
return k < 5 || trailingZeroes(lower_bound(4L * k, 5L * k, [k, this](long m) -> bool {
return trailingZeroes(m) >= k;
})) == k ? 5 : 0;
}
int trailingZeroes(long n) {
int r = 0;
while (n >= 5) {
n /= 5;
r += n;
}
return r;
}
long lower_bound(long l, long r, function<bool(long)> cb) {
while (l <= r) {
long m = (l + r) / 2;
if (cb(m)) r = m - 1;
else l = m + 1;
}
return l;
}
};int trailingZeroes(long n) {
int r = 0;
while (n >= 5) {
n /= 5;
r += n;
}
return r;
}
bool cb(long m, int* k) {
return trailingZeroes(m) >= *k;
}
long lower_bound(long l, long r, bool (*cb)(long, int*), int* k) {
while (l <= r) {
long m = (l + r) / 2;
if (cb(m, k)) r = m - 1;
else l = m + 1;
}
return l;
}
int preimageSizeFZF(int k){
return k < 5 || trailingZeroes(lower_bound(4L * k, 5L * k, cb, &k)) == k ? 5 : 0;
}class Solution:
def preimageSizeFZF(self, k: int) -> int:
def trailingZeroes(n: int):
r, divisor = 0, 5
while divisor <= n:
r += n // divisor
divisor *= 5
return r
return 5 if k < 5 or trailingZeroes(bisect_left(range(5 * k), k, key=trailingZeroes)) == k else 0class Solution(object):
def preimageSizeFZF(self, k): # python 2 自行实现 lower_bound
return 5 if k < 5 or self.trailingZeroes(self.lower_bound(0 * k, 5 * k, lambda m: self.trailingZeroes(m) >= k)) == k else 0
def trailingZeroes(self, n):
r, divisor = 0, 5
while divisor <= n:
r += n // divisor
divisor *= 5
return r
def lower_bound(self, l, r, cb):
while l <= r:
m = (l + r) // 2
if cb(m): r = m - 1
else: l = m + 1
return l