Iterative Python solution WITH EXPLANATION


  • 7

    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
            return tot

  • 0
    L

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


  • 0

    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.


Log in to reply
 

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