Preimage Size of Factorial Zeroes Function

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 two zeroes at the end.

Given an integer k, return the number of non-negative integers x have the property that f(x) = k.

Input & Output

Example 1 — Basic Case

$ Input: k = 3

› Output: 5

💡 Note: f(15) = f(16) = f(17) = f(18) = f(19) = 3, so exactly 5 numbers give 3 trailing zeros

Example 2 — Special Case Zero

$ Input: k = 0

› Output: 1

💡 Note: Only f(0) = 0, since 0! = 1 has no trailing zeros. All other factorials have trailing zeros.

Example 3 — Impossible Value

$ Input: k = 4

› Output: 0

💡 Note: No factorial has exactly 4 trailing zeros. The count jumps from 3 to 7, skipping 4,5,6.

Constraints

0 ≤ k ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input k

Target number of trailing zeros

Search Pattern

f(x) increases but skips values

Count Results

Return 0, 1, or 5

Key Takeaway

🎯 Key Insight: Factorial trailing zeros have gaps - some counts are impossible, others appear exactly 5 times consecutively!

Asked in

G Google 15 M Microsoft 8

Brief HTML summary: The key insight is that factorial trailing zeros come from factors of 10 = 2×5, and there are always more factors of 2 than 5, so we count factors of 5. The function f(x) is monotonically increasing but has gaps - some values are impossible. Best approach uses binary search to find boundaries efficiently. Time: O(log²k), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Linear Search	O(k × log k)	O(1)	Check every number until we find the range with exactly k trailing zeros
Binary Search on Answer Space	O(log²k)	O(1)	Use binary search to find the boundaries where f(x) = k

Brute Force Linear Search — Algorithm Steps

Step 1: For each x starting from 0, calculate f(x) = trailing zeros in x!
Step 2: When f(x) = k, count consecutive numbers with same trailing zero count
Step 3: Return the count (always 0 or 5)

Visualization

Tap to expand

Step-by-Step Walkthrough

Check f(0), f(1), f(2)...

Count trailing zeros in each factorial

Find matching count

Look for numbers where f(x) = k

Count occurrences

Return 0, 1, or 5 based on pattern

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int countTrailingZeros(int n) {
    int count = 0;
    for (int i = 5; i <= n; i *= 5) {
        count += n / i;
    }
    return count;
}

int solution(int k) {
    if (k == 0) {
        return 1;  // Only f(0) = 0
    }
    
    // Find first x where f(x) >= k
    int x = 0;
    while (countTrailingZeros(x) < k) {
        x++;
    }
    
    // Check if any x gives exactly k trailing zeros
    if (countTrailingZeros(x) == k) {
        return 5;  // Always 5 consecutive numbers
    } else {
        return 0;  // k is impossible
    }
}

int main() {
    int k;
    scanf("%d", &k);
    printf("%d\n", solution(k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k × log k)

Need to check up to 5k numbers, each taking O(log k) time to count factors of 5

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

12.0K Views

Medium Frequency

~25 min Avg. Time

450 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Linear Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler