Press "Enter" to skip to content

Posts tagged as “Factorial”

花花酱 LeetCode 172. Factorial Trailing Zeroes

By zxi on March 6, 2018

题目大意：求n!末尾0的个数。

Problem:

https://leetcode.com/problems/factorial-trailing-zeroes/description/

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

Idea:

All trailing zeros are come from even_num x 5, we have more even_num than 5, so only count factor 5.

4! = 1x2x3x4 = 24, we haven’t encountered any 5 yet, so we don’t have any trailing zero.

5! = 1x2x3x4x5 = 120, we have one trailing zero. either 2×5, or 4×5 can contribute to that zero.

9! = 362880, we only encountered 5 once, so 1 trailing zero as expected.

10! = 3628800, 2 trailing zeros, since we have two numbers that have factor 5, one is 5 and the other is 10 (2×5)

What about 100! then?

100/5 = 20, we have 20 numbers have factor 5: 5, 10, 15, 20, 25, …, 95, 100.

Is the number of trailing zero 20? No, it’s 24, why?

Within that 20 numbers, we have 4 of them: 25 (5×5), 50 (2x5x5), 75 (3x5x5), 100 (4x5x5) that have an extra factor of 5.

So, for a given number n, we are looking how many numbers <=n have factor 5, 5×5, 5x5x5, …

Summing those numbers up we got the answer.

e.g. 1000! has 249 trailing zeros:

1000/5 = 200

1000/25 = 40

1000/125 = 8

1000/625 = 1

200 + 40 + 8 + 1 = 249

alternatively, we can do the following

1000/5 = 200

200/5 = 40

40/5 = 8

8/5 = 1

1/5 = 0

200 + 40 + 8 + 1 + 0 = 249

Solution 1: Recursion

Time complexity: O(log5(n))

Space complexity: O(log5(n))

C++

Java

Python3

Related Problems:

花花酱 LeetCode 793. Preimage Size of Factorial Zeroes Function

By zxi on March 4, 2018

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 2 zeroes at the end. Given K, find how many non-negative integers x have the property that f(x) = K.

Note:

  • K will be an integer in the range [0, 10^9].

Idea:

First we need to compute how many trailing zeros n! has.

See  花花酱 LeetCode 172. Factorial Trailing Zeroes for details

It’s hard to say how many numbers have trailing zeros equals to K, but we can find the largest number p whose trailing zeros is K using binary search. (p+1)! has more than K trailing zeros. And do the same thing to find the largest number q whose trailing zeros is K – 1 using binary search.

Then we know that are exact p numbers 1,2,…,p whose trailing zeros are less or equal to K.

And exact q numbers 1, 2, …, q whose trailing zeros are less or equal to K – 1.

q + 1, q + 2, …, m (m – q numbers in total) the numbers with trailing zeros equal to K.

Solution 1: Math + Binary Search

Time complexity: O(log2(INT_MAX)*log5(INT_MAX))

Space complexity: O(1)

C++