Simple C/C++ Solution (with detailed explaination)


  • 177
    H

    The idea is:

    1. The ZERO comes from 10.
    2. The 10 comes from 2 x 5
    3. And we need to account for all the products of 5 and 2. likes 4×5 = 20 ...
    4. So, if we take all the numbers with 5 as a factor, we'll have way more than enough even numbers to pair with them to get factors of 10

    Example One

    How many multiples of 5 are between 1 and 23? There is 5, 10, 15, and 20, for four multiples of 5. Paired with 2's from the even factors, this makes for four factors of 10, so: 23! has 4 zeros.

    Example Two

    How many multiples of 5 are there in the numbers from 1 to 100?

    because 100 ÷ 5 = 20, so, there are twenty multiples of 5 between 1 and 100.

    but wait, actually 25 is 5×5, so each multiple of 25 has an extra factor of 5, e.g. 25 × 4 = 100,which introduces extra of zero.

    So, we need know how many multiples of 25 are between 1 and 100? Since 100 ÷ 25 = 4, there are four multiples of 25 between 1 and 100.

    Finally, we get 20 + 4 = 24 trailing zeroes in 100!

    The above example tell us, we need care about 5, 5×5, 5×5×5, 5×5×5×5 ....

    Example Three

    By given number 4617.

    5^1 : 4617 ÷ 5 = 923.4, so we get 923 factors of 5

    5^2 : 4617 ÷ 25 = 184.68, so we get 184 additional factors of 5

    5^3 : 4617 ÷ 125 = 36.936, so we get 36 additional factors of 5

    5^4 : 4617 ÷ 625 = 7.3872, so we get 7 additional factors of 5

    5^5 : 4617 ÷ 3125 = 1.47744, so we get 1 more factor of 5

    5^6 : 4617 ÷ 15625 = 0.295488, which is less than 1, so stop here.

    Then 4617! has 923 + 184 + 36 + 7 + 1 = 1151 trailing zeroes.

    C/C++ code

    int trailingZeroes(int n) {
        int result = 0;
        for(long long i=5; n/i>0; i*=5){
            result += (n/i);
        }
        return result;
    }
    

    ---------update-----------

    To avoid the integer overflow as @localvar mentioned below(in case of 'n >=1808548329' ), the expression " i <= INT_MAX/5" is not a good way to prevent overflow, because 5^13 is > INT_MAX/5 and it's valid.

    So, if you want to use "multiply", consider define the 'i' as 'long long' type.

    Or, take the solution @codingryan mentioned in below answer!


  • 0
    L
    This post is deleted!

  • 0
    This post is deleted!

  • 28
    C
    int trailingZeroes(int n) {
        int sum=0;
    	int tmp=0;
    	while(n/5>0)
    	{
    		tmp=n/5;
    		sum+=tmp;
    		n=tmp;
        }
        return sum;
     }
    

    explanation:http://www.purplemath.com/modules/factzero.htm


  • 0
    This post is deleted!

  • 2

    +1. Excellent analysis and very detailed thought process. Welcome to Discuss, @haoel!


  • 0
    L

    good explaination, Hao. but there's a small mistake, will get wrong answer when 'n >=1808548329' because of integer overflow. And leetcode are currently lack this case


  • 0
    H

    Yes, you are right. in your case, we need check the integer overflow in for-loop: i <= INT_MAX/5


  • 0
    L

    still problem because 5^13 > INT_MAX/5 and valid, maybe the best way is to use divide instead of multiply


  • 0
    H

    Oh, yes! if we need to use multiply, it seems we have to use "long long".


  • 0
    S

    Kudos for detailed analysis and expansion with generous examples.


  • 0

    @localvar: Excellent observation. I have just added your suggested test case. Thanks!


  • 0
    G

    Thanks for your explanation!!


  • 0
    E

    optimized to 3ms:

    int trailingZeroes(int n)
    {
    int sum=0;

    while(n>0)
    {
        n=n/5;
        sum+=n;
    }
    
    return sum;
    

    }


  • 0
    S

    excellent! How do you come up with this solution?


  • 0
    J

    Great explanation!! It's so easy to understand!! I just add the python version.

    def trailingZeroes(self, n):
        # return n/5 + n/25 + n/125 + ... + n/(5^13)
        return sum([ n/(5**i) for i in range(1, 14) ])

  • 0
    R

    actually your solution is 8 ms @ engkfke

    this is optimized

    for(int res=0;;res+=(n/=5)) if(n==0) return res;

  • 0

    I remember I've seen your article years ago. Are you work at Alibaba right now? // off the topic.


  • 0
    D

    Thank you for your explanation!


  • 0
    J

    Really nice explanation, I forgot the situation of extra '5' induced by numbers like 25, appreciate it.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.