Leetcode 0172 Factorial Trailing Zeroes

Problem statement

https://leetcode.com/problems/factorial-trailing-zeroes/

Solution

Use the formula $\left\lfloor \dfrac{n}{5}\right\rfloor + \left\lfloor \dfrac{n}{25}\right \rfloor + \dots.$

Complexity

It is O(log n) for time and O(1) for space.

Code

class Solution:
    def trailingZeroes(self, n):
        q, ans = 5, 0
        while q <= n:
            ans += n//q
            q *= 5
            
        return ans