โ† Salesforce questions
CodingReported in a candidate post, Jul 2023

Smallest Number With At least N Trailing Zeros In Factorial

Filed under Salesforce

Free read 2 of 3

Understand that trailing zeros in a factorial are determined by the number of factors of 5 in the prime factorization of numbers up to x.

The question

Given a positive integer N, find the smallest non-negative integer x such that x! contains at least N trailing zeros.

Constraints

  • 1 <= N <= 10^9
  • Time complexity must be better than O(x) linear scan

Examples

Input
N = 6
Output
25
Why
25! has 6 trailing zeros (factors of 5 from 5, 10, 15, 20, 25 give 6 factors of 5).

Approach

  1. Understand that trailing zeros in a factorial are determined by the number of factors of 5 in the prime factorization of numbers up to x.

Solution

O(log(5N) * log_5(N)) time, O(1) space

Python
class Solution:
    def smallestFactorial(self, n: int) -> int:
        def count_zeros(num):
            count = 0
            div = 5
            while num >= div:
                count += num // div
                div *= 5
            return count
        
        low, high = 0, 5 * n
        ans = high
        while low <= high:
            mid = (low + high) // 2
            if count_zeros(mid) >= n:
                ans = mid
                high = mid - 1
            else:
                low = mid + 1
        return ans

Tips

  • What they are testing: Tests ability to combine math properties (Legendre's formula) with binary search.
  • Common mistake: Linear scanning from 1 upwards, which results in Time Limit Exceeded (TLE).

Related Salesforce questions

Collected from public candidate posts and coding forums. Updated Nov 2026.