{"id":1998,"date":"2018-03-06T21:06:27","date_gmt":"2018-03-07T05:06:27","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=1998"},"modified":"2018-03-15T23:47:52","modified_gmt":"2018-03-16T06:47:52","slug":"leetcode-172-factorial-trailing-zeroes","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/math\/leetcode-172-factorial-trailing-zeroes\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 172. Factorial Trailing Zeroes"},"content":{"rendered":"

\u9898\u76ee\u5927\u610f\uff1a\u6c42n!\u672b\u5c3e0\u7684\u4e2a\u6570\u3002<\/p>\n

Problem:<\/h1>\n

https:\/\/leetcode.com\/problems\/factorial-trailing-zeroes\/description\/<\/a><\/p>\n

Given an integer\u00a0n<\/i>, return the number of trailing zeroes in\u00a0n<\/i>!.<\/p>\n

Note:\u00a0<\/b>Your solution should be in logarithmic time complexity.<\/p>\n

Idea:<\/strong><\/h1>\n

All trailing zeros are come from even_num x 5, we have more even_num than 5, so only count factor 5.<\/p>\n

4! = 1x2x3x4 = 24, we haven’t encountered any 5 yet, so we don’t have any trailing zero.<\/p>\n

5! = 1x2x3x4x5 = 120, we have one trailing zero. either 2×5, or 4×5 can contribute to that zero.<\/p>\n

9! =\u00a0362880, we only encountered 5 once, so 1 trailing zero as expected.<\/p>\n

10! =\u00a03628800, 2 trailing zeros, since we have two numbers that have factor 5, one is 5 and the other is 10 (2×5)<\/p>\n

What about 100! then?<\/p>\n

100\/5 = 20, we have 20 numbers have factor 5: 5, 10, 15, 20, 25, …, 95, 100.<\/p>\n

Is the number of trailing zero 20? No, it’s 24, why?<\/p>\n

Within that 20 numbers, we have 4 of them: 25 (5×5), 50 (2x5x5), 75 (3x5x5), 100 (4x5x5) that have an extra factor of 5.<\/p>\n

So, for a given number n, we are looking how many numbers <=n have factor 5, 5×5, 5x5x5, …<\/p>\n

Summing those numbers up we got the answer.<\/p>\n

e.g. 1000! has 249 trailing zeros:<\/p>\n

1000\/5 = 200<\/p>\n

1000\/25 = 40<\/p>\n

1000\/125 = 8<\/p>\n

1000\/625 = 1<\/p>\n

200 + 40 + 8 + 1 = 249<\/p>\n

alternatively, we can do the following<\/p>\n

1000\/5 = 200<\/p>\n

200\/5 = 40<\/p>\n

40\/5 = 8<\/p>\n

8\/5 = 1<\/p>\n

1\/5 = 0<\/p>\n

200 + 40 + 8 + 1 + 0 = 249<\/p>\n

Solution 1: Recursion<\/strong><\/h1>\n

Time complexity: O(log5(n))<\/p>\n

Space complexity:\u00a0O(log5(n))<\/p>\n

C++<\/h2>\n
\/\/ Author: Huahua\r\n\/\/ Running time: 4 ms\r\nclass Solution {\r\npublic:\r\n  int trailingZeroes(int n) {\r\n    return n < 5 ? 0 : n \/5 + trailingZeroes(n \/ 5);\r\n  }\r\n};<\/pre>\n
Java<\/h2>\n
\/\/ Author: Huahua\r\n\/\/ Running time: 1 ms\r\nclass Solution {\r\n  public int trailingZeroes(int n) {\r\n    return n < 5 ? 0 : n \/5 + trailingZeroes(n \/ 5);\r\n  }\r\n}<\/pre>\n
Python3<\/h3>\n
\"\"\"\r\nAuthor: Huahua\r\nRunning time: 68 ms\r\n\"\"\"\r\nclass Solution:\r\n  def trailingZeroes(self, n):\r\n    return 0 if n < 5 else n \/\/ 5 + self.trailingZeroes(n \/\/ 5)<\/pre>\n
Related Problems:<\/strong><\/h1>\n