LeetCode - Algorithms - 172. Factorial Trailing Zeroes

Problem

172. Factorial Trailing Zeroes

Java

solution of geeksforgeeks © Count trailing zeroes in factorial of a number

1
2
3
4
5
6
7
8
class Solution {
    public int trailingZeroes(int n) {
        int count = 0;
        for (long i = 5; i <= n; i *= 5)
            count += n / i;
        return count;
    }
}

Submission Detail

  • 502 / 502 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Factorial Trailing Zeroes.
  • Memory Usage: 36.6 MB, less than 31.99% of Java online submissions for Factorial Trailing Zeroes.

my solution

Accepted until 4th submission.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int trailingZeroes(int n) {
        if (n == 0)
            return 0;
        Double d = Math.floor((Math.log(n)) / (Math.log(5)));
        int m = d.intValue();
        int x = 0;
        for (int i = 1; i <= m; i++) {
            x += n / Math.pow(5, i);
        }
        return x;
    }
}

Submission Detail

  • 502 / 502 test cases passed.
  • Runtime: 1 ms, faster than 20.14% of Java online submissions for Factorial Trailing Zeroes.
  • Memory Usage: 36.6 MB, less than 39.00% of Java online submissions for Factorial Trailing Zeroes.

my solution - 2

a one line function logarithm(n, r) which returns \( \lfloor \log_r n \rfloor \). © Program to compute Log n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int trailingZeroes(int n) {
        if (n < 5)
            return 0;
        int m = logarithm(n,5);
        int x = 0;
        for (int i = 1; i <= m; i++) {
            x += n / Math.pow(5, i);
        }
        return x;
    }
    
    private int logarithm(int n, int r) {
        return (n > r - 1) ? 1 + logarithm(n / r, r) : 0;
    }
}

Submission Detail

  • 502 / 502 test cases passed.
  • Runtime: 1 ms, faster than 19.86% of Java online submissions for Factorial Trailing Zeroes.
  • Memory Usage: 38.6 MB, less than 5.16% of Java online submissions for Factorial Trailing Zeroes.

my solution - 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int trailingZeroes(int n) {
        if (n < 5)
            return 0;
        long x = 0;
        long p = 5;
        while (n >= p) {
            x += n / p;
            p *= 5;
        }
        Long l = new Long(x);
        return l.intValue();
    }
}

Submission Detail

  • 502 / 502 test cases passed.
  • Runtime: 1 ms, faster than 19.86% of Java online submissions for Factorial Trailing Zeroes.
  • Memory Usage: 36 MB, less than 94.80% of Java online submissions for Factorial Trailing Zeroes.

my solution - 4

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int trailingZeroes(int n) {
        if (n < 5)
            return 0;
        int x = 0;
        for (long p = 5; n >= p; ) {
            x += n / p;
            p *= 5;
        }
        return x;
    }
}

Submission Detail

  • 502 / 502 test cases passed.
  • Runtime: 2 ms, faster than 19.86% of Java online submissions for Factorial Trailing Zeroes.
  • Memory Usage: 38.1 MB, less than 10.66% of Java online submissions for Factorial Trailing Zeroes.