LeetCode / Factorial Trailing Zeroes

今日は算数の問題です。大人より小学生の方が解けるかも？

[https://leetcode.com/problems/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.

nの階乗で得られた数値に、trailing zero、つまり後置の0がいくつあるかを返す問題です。
空間計算量のオーダーを$log(n)$とすることも求められています。つまり、馬鹿正直にnの階乗を計算するのではない方法が求められます。

解答・解説

解法1

まず気付くべきは、「後置の0が幾つ存在するかは、nの階乗の中で10が何回掛けられるかと同値である」です。
次に気付くべきは、10を素因数分解すると2×5ですから、「後置の0が幾つ存在するかは、nの階乗に2が幾つ存在するか（2で何回割り切れるか）と5が幾つ存在するか（2で何回割り切れるか）の最小値と同値である」です。
そして当然、2で割り切れる回数と5で割り切れる回数では後者の方が小さいですから、5で割り切れる回数を計算すれば、それが答えになります。

さて、以上の考察をそのままコードに落とすと、以下のようになります。

class Solution(object):
    def trailingZeroes(self, n):
        """
        :type n: int
        :rtype: int
        """
        ans = 0
        while n > 0:
            n //= 5
            ans += n
        return ans

上記コードの中では、5で割り切っているわけではなく5で割った商を足し合わせています。5で割り切るコードよりも短く書けます。横着とも言います。
空間計算量はlog₅ⁿになります。

ちなみにPython2だとint同士の割り算はintが返るんですね。上記も n /= 5 としても正解が得られます。知らなかった。。。

解法2

recursiveに書くこともできます。計算量は変わりません。

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