Problem

Let f(x) be the number of zeroes at the end of x!. Recall that `x! = 1 * 2

  • 3 * … * xand 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.

Examples

Example 1

1
2
3

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

Example 2

1
2
3

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

Example 3

1
2

Input: k = 3
Output: 5

Constraints

  • 0 <= k <= 10^9

Solution

Method 1 - Binary Search on Zeta Function

Intuition

The number of trailing zeroes in x! is determined by the number of times 5 divides numbers up to x. For a given k, we want to count how many x satisfy f(x) = k. It turns out that for any k, the set of x with f(x) = k is either 0 or 5 consecutive numbers. We can use binary search on the zeta function f(x) to find the leftmost and rightmost x such that f(x) = k.

Approach

Define a function f(x) that returns the number of trailing zeroes in x!. For a given k, the answer is the number of x such that f(x) = k, which we can denote as f_inv(k) = count(x | f(x) = k). This is equal to (right - left), where left is the smallest x with f(x) = k, and right is the smallest x with f(x) = k+1.

Complexity

  • ⏰ Time complexity: O(log^2(k)) due to binary search and repeated division.
  • 🧺 Space complexity: O(1)

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

int zeta(int x) {
    int res = 0;
    while (x) {
        res += x / 5;
        x /= 5;
    }
    return res;
}
int preimageSizeFZF(int k) {
    auto left = [](int k) {
        long l = 0, r = 5L * k + 5;
        while (l < r) {
            long m = l + (r - l) / 2;
            int z = 0, x = m;
            while (x) { z += x / 5; x /= 5; }
            if (z < k) l = m + 1;
            else r = m;
        }
        return l;
    };
    return (int)(left(k+1) - left(k));
}
 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
26
27
28

func zeta(x int) int {
    res := 0
    for x > 0 {
        res += x / 5
        x /= 5
    }
    return res
}
func left(k int) int {
    l, r := 0, 5*k+5
    for l < r {
        m := l + (r-l)/2
        z, x := 0, m
        for x > 0 {
            z += x / 5
            x /= 5
        }
        if z < k {
            l = m + 1
        } else {
            r = m
        }
    }
    return l
}
func preimageSizeFZF(k int) int {
    return left(k+1) - left(k)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    private int zeta(int x) {
        int res = 0;
        while (x > 0) {
            res += x / 5;
            x /= 5;
        }
        return res;
    }
    private long left(int k) {
        long l = 0, r = 5L * k + 5;
        while (l < r) {
            long m = l + (r - l) / 2;
            int z = 0, x = (int)m;
            while (x > 0) { z += x / 5; x /= 5; }
            if (z < k) l = m + 1;
            else r = m;
        }
        return l;
    }
    public int preimageSizeFZF(int k) {
        return (int)(left(k+1) - left(k));
    }
}
 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
26

fun zeta(x: Int): Int {
    var res = 0
    var x0 = x
    while (x0 > 0) {
        res += x0 / 5
        x0 /= 5
    }
    return res
}
fun left(k: Int): Long {
    var l = 0L
    var r = 5L * k + 5
    while (l < r) {
        val m = l + (r - l) / 2
        var z = 0
        var x = m
        while (x > 0) {
            z += (x / 5).toInt()
            x /= 5
        }
        if (z < k) l = m + 1
        else r = m
    }
    return l
}
fun preimageSizeFZF(k: Int): Int = (left(k+1) - left(k)).toInt()
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

def zeta(x: int) -> int:
    res = 0
    while x:
        res += x // 5
        x //= 5
    return res

def left(k: int) -> int:
    l, r = 0, 5 * k + 5
    while l < r:
        m = (l + r) // 2
        z, x = 0, m
        while x:
            z += x // 5
            x //= 5
        if z < k:
            l = m + 1
        else:
            r = m
    return l

def preimageSizeFZF(k: int) -> int:
    return left(k+1) - left(k)
 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
26
27
28
29

fn zeta(mut x: i64) -> i64 {
    let mut res = 0;
    while x > 0 {
        res += x / 5;
        x /= 5;
    }
    res
}
fn left(k: i64) -> i64 {
    let (mut l, mut r) = (0, 5 * k + 5);
    while l < r {
        let m = l + (r - l) / 2;
        let mut z = 0;
        let mut x = m;
        while x > 0 {
            z += x / 5;
            x /= 5;
        }
        if z < k {
            l = m + 1;
        } else {
            r = m;
        }
    }
    l
}
fn preimage_size_fzf(k: i64) -> i64 {
    left(k+1) - left(k)
}
 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

function zeta(x: number): number {
    let res = 0;
    while (x > 0) {
        res += Math.floor(x / 5);
        x = Math.floor(x / 5);
    }
    return res;
}
function left(k: number): number {
    let l = 0, r = 5 * k + 5;
    while (l < r) {
        let m = Math.floor((l + r) / 2);
        let z = 0, x = m;
        while (x > 0) {
            z += Math.floor(x / 5);
            x = Math.floor(x / 5);
        }
        if (z < k) l = m + 1;
        else r = m;
    }
    return l;
}
export function preimageSizeFZF(k: number): number {
    return left(k+1) - left(k);
}