Accepted O(log5(N)) Python solution


  • 1
    X
    class Solution:
        # @return an integer
        def trailingZeroes(self, n):
            div = 5
            result = 0
            while div <= n:
                result += n//div
                div = div*5
            return result
    

    Updated Version with additional checking for overflow. Thanks to @adamlhh for pointing this out!

    class Solution:
        # @return an integer
        def trailingZeroes(self, n):
            div = 5
            result = 0
            while div <= n:
                result += n//div
                if div > (0x7FFFFFFF/5):
                    break
                div = div*5
            return result

  • 0
    A

    Same idea implemented in Java. I wonder how python does not need to check for overflow..

    public int trailingZeroes(int n) {
            int total = 0;
            int div = 5;
            while (div <= n) {
                total += (int)(n/div);
                if (div > Integer.MAX_VALUE/5) {
                    break;
                }
                div *= 5;
            }
            return total;
        }

  • 0
    J

    in c++

    class Solution {
    public:
    int trailingZeroes(int n) {
    int ct=0;
    while(n) {
    ct += n/5;
    n = n/5;
    }
    return ct;
    }
    };


  • 0
    X

    Oh, do we need to worry about overflow?I guess the test cases on leetcode didn't include overflow situations. So I didn't even think of that. Thanks for pointing out!


  • 0
    P

    Similar to my solution, however I didn't notice the overflow issue. It's not included in the test cases, right? Thanks for sharing.


Log in to reply
 

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