O(1) and 1 line solution in Java, Python, C


  • -3
    G
    return n/5 + n/25 + n/125 + n/625 + n/3125;
    

    The number of trailing zeros is equal to how many factors of 10 can be found in 'factorial n'.

    The prime factors of 10 is 5 and 2.
    Also, in any factorial the number of factors of 2 >= number of factors of 5.
    Thus, all I need to do is find the number of factors of 5.

    My code does this by finding the number of factors divisible by 5 once (n/5) and adding the number of factors divisible by 5 twice (n/25) and so on.

    P.S. this code only works for numbers under 15,625 or 5^6--which is out of range of the problem's input.
    This is easily fixed by adding n/15625 and n divided by increasing powers of 5.


  • 0
    S

    Brilliant!!!


  • -1
    L

    I don't think this one is O1). for example, can we deem below code as O(1)? because the maximum iteration count is 13, which is a constant

    int c = 0, d = 5;
    for( int i = 0; i < 13; ++i, d *= 5 )
        c += n / d;
    return c;
    

    if yes, what's the time complexity of below code:

    int c = 0;
    for( ; n > 4; c += (n/=5) );
    return c;
    

    if we think this one is O(log(n)), why an O(log(n)) solution always faster (at least not slower) than an O(1) solution?


  • 0
    D

    I used the same method, but I wrote it in a loop

    class Solution {
    public:
    	int trailingZeroes(int n) {
    		int result = 0;
    		for (__int64 i = 5; i <= n; i *= 5){
    			result += n / i;
    		}
    		return result;
    	}
    };

  • 0
    C

    Could u please explain why should 13 be ok? I tried 14 and 15, not work


  • 0
    L

    integer overflow, 5^13 < 2^31 < 5^14


  • 0
    M

    Why do you stop at 3125?!!


Log in to reply
 

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