Solution by rohitnandi12


  • 0
    R

    Primary Thoughts

    What is Factorial of a number N ?

    Factorial of a number N is denoted as N! and is the product of the all the number from 1 to N inclusive. Factorial of non positive number is 1.
    e.g 5! = 5 x 4 x 3 x 2 x 1 = 120 . 0! = 1 , -2! = 1.

    Product of two numbers will have zero at the end only when it has both 2 and 5 as one its prime factors. Hence if get to know the number of 2s and 5s int the factorial, then number of trailing zeros will be Max(2s count, 5s count).

    As a matter of fact, the number of 2 are always greater than number of 5s in the prime factorization of a number. Hence counting the number of 5s will do.

    Test Cases

    Try to create your own test cases. You can take help of the interviewer, to validate your understanding of the problem.

    T1 : -1           // 0
    T2 : 0            // 0
    T3 : 1            // 0
    T4 : 5            // 1
    T4 : 2147483647   // 536870902
    
    

    Approach #1 [Overflow]

    Intuition

    We can evaluate the factorial and then count the number of trailing zeros. This approach is simple but will cause overflow for N>16.


    Approach #2 Implementation [Accepted]

    Trailing 0s in n!
    = Count of 5s in prime factors of n!
    = floor(n/5) + floor(n/25) + floor(n/125) + ...

    Java

    class Solution {
        public int trailingZeroes(int n) {
            int f=5,c=0;
    
            while(f<=n){
                c += n/f;
                if(f>2147483647/5)break;
                f *= 5;
    
            }
            return c;
        }
    }
    

    Complexity Analysis

    • Time complexity : $$O(n).

    • Space complexity : $$O(1)$$.

    Thank You for your up vote. Happy Coding :-)


Log in to reply
 

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