My explanation of the Log(n) solution


  • 118
    G

    10 is the product of 2 and 5. In n!, we need to know how many 2 and 5, and the number of zeros is the minimum of the number of 2 and the number of 5.

    Since multiple of 2 is more than multiple of 5, the number of zeros is dominant by the number of 5.

    Here we expand

      2147483647!
    =2 * 3 * ...* 5 ... *10 ... 15* ... * 25 ... * 50 ... * 125 ... * 250...
    =2 * 3 * ...* 5 ... * (5^1*2)...(5^1*3)...*(5^2*1)...*(5^2*2)...*(5^3*1)...*(5^3*2)... (Equation 1)
    

    We just count the number of 5 in Equation 1.

    Multiple of 5 provides one 5, multiple of 25 provides two 5 and so on.

    Note the duplication: multiple of 25 is also multiple of 5, so multiple of 25 only provides one extra 5.

    Here is the basic solution:

    return n/5 + n/25 + n/125 + n/625 + n/3125+...;
    

    You can easily rewrite it to a loop.


  • 0
    C

    nice and clean explanation!


  • 2
    L

    Following the above explanation, here is the accepted code.

    public int trailingZeroes(int n) {
    	int power = 1;
    	int c = 0;
    	int f = (int) (n/(Math.pow(5, power)));
    	
    	while(f > 0){
    		c += f;
    		f = (int) (n/(Math.pow(5, ++power)));
    	}
    	
    	return c;
    }
    

  • 30
    P

    Concise implementation.

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

  • 0
    X

    can u explain why is this solution log(n) instead of O(n)?


  • 1
    J

    The loop runs log5N times.


  • 0

    Thanks for sharing! It helps a lot!


  • 1

    @jyc1992 any time your solution is reducing by a factor greater than 1 it is log time with the log base being your factor. In this case you are reducing by a factor of 5 each loop so you have O(log5 N) <- that is meant to be "log N with base 5". You could be reducing by a factor of 2 or 10 or 50 that is still log time.


  • 2
    M

    Great explanation here. But I would like to reiterate the same idea in a slightly elaborate manner.

    As mentioned above, the idea is to count the number of 5s. It's almost as if we are placing all the elements in the factorial sequence within an array, and dividing every element by 5. This division is only done if the element is multiple of 5. Total number of such divisions should give us the number of 5s, and hence the number of trailing zeros also. This would be O(n) space and O(n) time complexity

                for (i = 1; i <= n; ++i) // populate the sequence
                        arr[i - 1] = i;
                do{
                    for (f = 0, i = 0; i < n; ++i)
                      if (!(arr[i] % 5)) // detect multiples of 5
                      {
                          count++; // count of 5s
                          f = 1;
                          arr[i] /= 5;
                      }
                } while (f);
                return count;
    

    The number of multiples of 5 within a factorial sequence can also be calculated by simply dividing the largest element by 5!

    So dividing a number 'n' by 5 gives the number of multiple of 5 within the range [1, n]. But if this range contains elements which are multiples of powers of 5, then the quotient (q) will also be greater than or equal to 5.

    Considering the equation n >= q x 5, if q >= 5, then n has to be greater than or equal to 25. So there is at least one 5 ^ 2 within the sequence.

    So, with the first division we count the number of multiples of 5 ^ 1, with the second we count the number of multiples of 5 ^ 2, then 5 ^ 3 and so on.

    Recursively applying this logic gives a call stack depth of Log5(n). Time complexity would be O(Log5(n)).

    int trailingZeroes(int n) {
      return n >= 5 ? n / 5 + trailingZeroes(n / 5) : 0;
    }
    

  • 0
    J

    @gqq

    Does anyone know why this solution is not working at input number: 1808548329? Thanks!

    input: 1808548329
    output: 452137080
    expected: 452137076

    I guess it is because of rounding issue.

    public int trailingZeroes(int n) {
            if (n < 0) 
                return -1;
           
            int count = 0;
            
            for (int i = 5; n / i > 0; i *= 5) {
                count += n / i;
            }
            
            return count;
    }
    

    It works when I tried with the solution posted by @pin2

    public int trailingZeroes(int n) {
            int cnt = 0;
            while(n>0){
                cnt += n/5;
                n/=5;
            }
            return cnt;
        }
    

    I started another thread:
    https://discuss.leetcode.com/topic/76800/rounding-issue


  • 2
    C

    @jun711 That's because 5^13 = 1220703125 < 2^31, but 5^14 = 6103515625 > 2^32. It overflows. So it's better using n/5 instead of i*=5.


  • 0
    F

    What I don't understand about any of these solutions is why aren't we counting 10, 20, 30, 40, etc, which all add a trailing zero?

    10! has 2 trailing zeroes, one for the 2*5 and one for the 10. Why are we only concerned with 2s and 5s?


Log in to reply
 

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