Step 1 - Trailing 0s in x! = Count of 5s in prime factors of x!
= floor(x/5) + floor(x/25) + floor(x/125) + ....
Step 2 - We can notice that, the maximum value whose factorial contain n trailing zeroes ...read more

• A brute force approach could be to generate factorials of numbers starting from 0.
• For every factorial, we find the number of trailing zeros. This can be done as follows:
  • Let fa...read more

• The brute force approach will not work for larger values of N. So, we need to find a better approach.
• If we observe, a trailing zero is produced by the multiplication of prime factors 2 and 5. Hence, we need at least one occurrence of 2 and 5 in the prime factorization of factorial to get a trailing zero.
• We can use this observation to find the pattern. Let’s see a few examples:
  • 0! (= 1) has no trailing zeros. Also, all the numbers from 0 to 4 have no trailing zeros, due to the absence of prime factors 2 and 5.
  • 5! (= 120) has one trailing zero. All the numbers from 5 to 9 have 1 trailing zero, due to the presence of prime factors 2 and 5, where 5 occurs only once.
  • Similarly, the factorial of numbers 10 to 14 have 2 trailing zeros.
  • Factorial of numbers 20 to 24 have 4 trailing zeros.
  • Factorial of numbers 25 to 29 have 6 trailing zeros (one extra because 25 has two fives in its prime factorization), and so on.
• From this, we can observe that the minimum value containing at least N trailing zeros is always less than or equal to 5*N.
• So we can apply a binary search in the range 0 to 5*N to find the smallest number.
• For every iteration in binary search, we need to check if the current number has at least N trailing zeros in its factorial. This can be found using the formula:
  • Trailing 0s in X! = Number of 5s in the prime factorization of X!
  • i.e Trailing 0s in X! = floor(X / 5) + floor(X / 25) + floor(X / 125) + .......
  • The above formula is derived using the observation that in the prime factorization of a factorial, the number of 5s is always less than the number of 2s. Hence, the number of trailing zeros only depends on the number of 5s. (For more information you can refer to a previously solved problem here).

Algorithm:

• Initialize two variables low and high to 0 and 5*N respectively. These are used in our binary search.
• Repeat the following steps until low < high:
  • Find the middle value, i.e. mid = (low + high)/2.
  • Check if the factorial of mid contains at least N trailing zeros. This can be done using the formula mentioned above. Let the number of trailing zeros in mid! be count.
  • If count >= N: Set high = mid. This means that mid can be our answer but we need to check if there is any other number smaller than mid and with count >= N.
  • Otherwise, set low = mid + 1. As, count < N, hence, mid cannot be our answer. So, we check for numbers greater than mid in hope of finding a number with count >= N.
• Return low.

O(1)

Only constant extra space is required.

O((log(N)) ^ 2), where N is the number of trailing zeroes.

Binary search on the range 0 to 5 * N requires O(log(N)) time. Also, for every iteration in binary search, we are calculating the count of trailing zeros for that number, which requires O(log(N)) time. Hence, the overall time complexity is O((log(N)) ^ 2).

'''
    Time complexity: O(log(N) ^ 2)
    Space complexity: O(1)
    
    Where N is the number of trailing zeros.
'''


def countTrailingZeros(x):
    '''
        Count the number of trailing zeros using the formula:
        Trailing 0s in X! = floor(X / 5) + floor(X / 25) + floor(X / 125) + ...
    '''
    count = 0
    div = 5

    while(div <= x):
        count += (x//div)

        div *= 5

    return count


def findSmallestNumber(n):
    low = 0
    high = 5*n

    # Apply Binary Search in the range [0, 5N].
    while(low < high):
        mid = low + (high - low) // 2

        # Find the number of trailing zeros in mid!.
        count = countTrailingZeros(mid)

        # Check if mid! contains at least N trailing zeros.
        if (count >= n):
            high = mid
        else:
            low = mid + 1
    
    return low

/*
    Time complexity: O(log(N) ^ 2)
    Space complexity: O(1)

    Where N is the number of trailing zeros.
*/

int countTrailingZeros(int x)
{
    // Count the number of trailing zeros using the formula:
    // Trailing 0s in X! = floor(X / 5) + floor(X / 25) + floor(X / 125) + ...

    int count = 0;
    int div = 5;

    while (div <= x)
    {
        count += (x / div);

        div = div * 5;
    }

    return count;
}

int findSmallestNumber(int n)
{
    int low = 0, high = 5 * n;

    // Apply Binary Search in the range [0, 5N].
    while (low < high)
    {
        int mid = low + (high - low) / 2;

        // Find the number of trailing zeros in mid!.
        int count = countTrailingZeros(mid);

        // Check if mid! contains at least N trailing zeros.
        if (count >= n)
        {
            high = mid;
        }
        else
        {
            low = mid + 1;
        }
    }

    return low;
}

/*
	Time complexity: O(log(N) ^ 2)
	Space complexity: O(1)

	Where N is the number of trailing zeros.
*/

public class Solution 
{

	public static int countTrailingZeros(int x) 
	{
		// Count the number of trailing zeros using the formula:
		// Trailing 0s in X! = floor(X / 5) + floor(X / 25) + floor(X / 125) + ...

		int count = 0;
		int div = 5;

		while (div <= x) 
		{
			count += (x / div);

			div = div * 5;
		}

		return count;
	}

	public static int findSmallestNumber(int n) 
	{
		int low = 0, high = 5 * n;

		// Apply Binary Search in the range [0, 5N].
		while (low < high) 
		{
			int mid = low + (high - low) / 2;

			// Find the number of trailing zeros in mid!.
			int count = countTrailingZeros(mid);

			// Check if mid! contains at least N trailing zeros.
			if (count >= n) 
			{
				high = mid;
			} else 
			{
				low = mid + 1;
			}
		}

		return low;
	}
}