Solution by ajitzero [3 approaches]


  • 0

    Approach #1 Brute force [Integer Overflow]

    Intuition

    According to the question, we first calculate the factorial of the number and then count the number of zeroes from the last digit (least significant bit) until we get a non-zero digit.

    Algorithm

    • Use a simple loop to compute the factorial by multiplying all numbers in the range $$1 to n$$.
    • Keep incrementing a counter variable, $$count$$ while the last digit is zero.

    C++

        class Solution {
        public:
            int trailingZeroes(int n) {
                long long int factorial = 1;
                for (int i = 1; i <= n; ++i) {
                    factorial *= i;
                }
                int count = 0;
                while (factorial % 10 == 0) {
                    ++count;
                    factorial /= 10;
                }
                return count;
            }
        };
    

    Python

        class Solution(object):
            def trailingZeroes(self, n):
                res = 1
                for i in xrange(1, n+1):
                    res *= i
                count = 0
                while res % 10 == 0:
                    count += 1
                    res /= 10
                return 
    

    Complexity Analysis

    • Time complexity : $$O(n + count) = O(n)$$. To compute the factorial we need at most $$n$$ iterations and then we count the trailing zeroes, which takes at most $$count$$ iterations. Thus, the time complexity is $$O(n)$$.

    • Space complexity : $$O(1)$$. We only need two variables for the factorial value and the counter variable.

    Note

    • For languages like Python which support arbitrarily large numbers, instead of encountering an integer overflow issue we face the Time Limit Exceeded error.
    • The factorial of a non-negative number $$n$$, denoted by $$n!$$, is the product of all positive integers in the inclusive range of $$1 to n$$. By convention, factorial of zero, $$0!$$ is $$1$$ and is undefined for negative numbers. For the purposes of this problem, we extend the convention of using 1 as the result for non-negative numbers.

    Approach #2 Mathematical simplification (Recursive) [Accepted]

    Intuition

    The number of trailing zeroes in $$n!$$ is the number of times $$10$$, i.e., $$2 * 5$$ is multiplied. Thus, we simply count all multiple of 5 less than or equal to $$n$$.

    Example:

    For $$1234!$$,

    • $$1234 / 5$$ gives $$246$$ multiples of 5.
    • $$246 / 5$$ gives $$49$$ multiples of 5.
    • $$49 / 5$$ gives $$9$$ multiples of 5.
    • $$9 / 5$$ gives $$1$$ multiples of 5.

    Thus, we compute and get $$246 + 49 + 9 + 1 = 305$$ trailing zeros.

    Algorithm

    • Let trailingZeroes(n) be a function.
    • If $$n$$ is zero, no more multiples of $$5$$ are left and return $$0$$.
    • While $$n$$ is not zero, return the sum of $$n/5$$ (current multiples) and the result of trailingZeroes(n/5) (remaining multiples).

    C++

        class Solution {
        public:
            int trailingZeroes(int n) {
                if (n == 0) {
                    return 0;
                }
                return n / 5 + trailingZeroes(n / 5);
            }
        };
    

    Python

        class Solution(object):
            def trailingZeroes(self, n):
                if n == 0:
                    return 0
                return n / 5 + self.trailingZeroes(n / 5)
    

    Complexity Analysis

    • Time complexity : $$O(log(n))$$. Division by 5 reduces the number of operations taking place for every power of 5. Thus, the time complexity is $$O(log(n))$$.

    • Space complexity : $$O(log_5(n))$$. Every recursive call is stored in a stack frame and thus, the space complexity is $$O(log(n))$$.


    Approach #3 Mathematical simplification (Iterative) [Accepted]

    Algorithm

    • Initialize $$ans$$ to $$0$$.
    • While $$n$$ is not less than $$5$$:
      • Divide $$n$$ by $$5$$ and update it.
      • Add $$n$$ to $$ans$$.

    C++

        class Solution {
        public:
            int trailingZeroes(int n) {
                int count = 0;
                while (n >= 5) {
                    n /= 5;
                    count += n;
                }
                return count;
            }
        };
    

    Python

        class Solution(object):
            def trailingZeroes(self, n):
                count = 0
                while n >= 5:
                    n /= 5
                    count += n
                return count
    

    Complexity Analysis

    • Time complexity : $$O(log(n))$$. Division by 5 reduces the number of operations taking place for every power of 5. Thus, the time complexity is $$O(log(n))$$.

    • Space complexity : $$O(1)$$. We only need one variable for the counter variable.

    Reference


    Analysis written by @ajitzero


Log in to reply
 

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