Iterative Python solution WITH EXPLANATION

• We add a trailing zero every time we multiply by 10 (5 * 2). Since we will have always more 2s than 5s, the problem is to find the number of 5s in the numbers from 1 to n.
Let's consider 10! as example:

10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1

In this case, we have two 5s (in 10 and 5), so the result is 2. How can we efficiently compute this number for a given n? Well, we could compute the multiple of 5 contained in n, but this is not enough: for example, 25 accounts for 2 5s, 50 accounts also for 2 5s, and so on.

So, we do the following: we start from 5, and we see how many multiples of 5 we have in n. Then, we multiply 5 by 5 (25) and we add how many multiples of 25 we have in n. In this case we will not have duplicates, as at in each step we will add only one 5 to the result.

``````class Solution(object):
def trailingZeroes(self, n):
k, tot = 5, 0
while k <= n:
tot += n // k
k = k * 5

• I used the same solution and wrote Java code, but the result is wrong for some big numbers, like 1899999999. Anyone know why?

public int trailingZeroes(int n) {
int k = 5;
int result = 0;
while(k <= n){
result += n/k;
k = k*5;
}
return result;
}

• Python supports a "bignum" integer type which can work with arbitrarily large numbers. In Python 2.5+, this type is called `long` and is separate from the `int` type, but the interpreter will automatically use whichever is more appropriate. In Python 3.0+, the `int` type has been dropped completely.

That's just an implementation detail, though — as long as you have version 2.5 or better, just perform standard math operations and any number which exceeds the boundaries of 32-bit math will be automatically (and transparently) converted to a bignum. You can find all the gory details in PEP 0237 (https://www.python.org/dev/peps/pep-0237/).

Java doesn't have this luxury and the version we have here works with 32-bit numbers. That's why it doesn't work.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.