Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/172.html

 172	Factorial Trailing Zeroes

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

 Example 1:

 Input: 3
 Output: 0
 Explanation: 3! = 6, no trailing zero.
 Example 2:

 Input: 5
 Output: 1
 Explanation: 5! = 120, one trailing zero.
 Note: Your solution should be in logarithmic time complexity.

 @tag-math

Algorithm

To find the number of 10 in the multiplier, and 10 can be decomposed into 2 and 5, and the number of 2 is much greater than the number of 5 (for example, there are 2 5s in 1 to 10, 5 2s), then this question is find the counts of 5.

One thing that still needs to be noted is that numbers like 25, 125, which contain more than a 5, need to be taken into consideration.

Code

  • 
    public class Factorial_Trailing_Zeroes {
    
        public static void main(String[] args) {
            Factorial_Trailing_Zeroes out = new Factorial_Trailing_Zeroes();
            Solution_iteration s = out.new Solution_iteration();
    
            s.trailingZeroes(126);
    //        System.out.println(s.trailingZeroes(126));
        }
    
    
        public class Solution_iteration {
            public int trailingZeroes(int n) {
                int res = 0;
                while (n > 0) {
                    res += n / 5;
                    n /= 5;
    
                    /*
                    System.out.println(res);
                        25
                        30
                        31
                        31
                    */
                }
                return res;
            }
        }
    
        class Solution {
            public int trailingZeroes(int n) {
                return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
            }
        }
    }
    
    ############
    
    class Solution {
        public int trailingZeroes(int n) {
            int ans = 0;
            while (n > 0) {
                n /= 5;
                ans += n;
            }
            return ans;
        }
    }
    
  • class Solution:
        def trailingZeroes(self, n: int) -> int:
            ans = 0
            while n:
                n //= 5
                ans += n
            return ans
    
    ############
    
    class Solution(object):
      def trailingZeroes(self, n):
        """
        :type n: int
        :rtype: int
        """
        count, k = 0, 5
        while n:
          k = n / 5
          count += k
          n = k
        return count
    
    
  • class Solution {
    public:
        int trailingZeroes(int n) {
            int ans = 0;
            for (int i = 5; i <= n; i *= 5) ans += n / i;
            return ans;
        }
    };
    
  • func trailingZeroes(n int) int {
    	ans := 0
    	for n > 0 {
    		n /= 5
    		ans += n
    	}
    	return ans
    }
    
  • function trailingZeroes(n: number): number {
        let ans = 0;
        while (n > 0) {
            n = Math.floor(n / 5);
            ans += n;
        }
        return ans;
    }
    
    

All Problems

All Solutions