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


  • 170
    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!


Log in to reply
 

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