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

Java

• Java
• C++
• Python

• 
  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);
          }
      }
  }
  

• Todo
  

• 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
  
  

All Problems

All Solutions