Straightforward Java Solution (with Explanation)


  • 1
    Y

    We know that among all numbers of factorial, only numbers with factor 2 and 5 can produce a trailing zero (2*5 = 10), and that we will have much more factor 2's than factor 5's. So the key is to find the number of factor 5's we have in the factorial sequence, which is equivalent to the number of trailing zeros (the final solution to this problem).

    I used an example to deduce the solution:
    Suppose n = 100, then how many numbers with factors 5 do we have?
    --> We have 1*5, 2*5, 3*5, ..., 20*5, a total of 100/5 = 20 numbers.
    Among the numbers 1-20, there also exists factor 5.
    --> We have 1*5, 2*5, ..., 4*5 a total of 20/5 = 4 numbers.
    And so on.

    Thus, given a number n, we can just repeat the following process:

    Repeat while n > 0
    1. Divide n by 5 to find numbers with factor 5 (add to result)
    2. Set n = n / 5 to find remaining factor 5's
    
    public class Solution {
        public int trailingZeroes(int n) {
            int result = 0;
            while (n > 0) {
                result += (n / 5);
                n /= 5;
            }
            return result;
        }
    }
    

  • 0
    D

    Thanks for your answer. I think we can improve the code on L:5.

    Here is the code

    public class Solution {
        public int trailingZeroes(int n) {        
            if(n < 0) return -1;        
            int result = 0;
            while(n > 1) {            
                result += (n /= 5);  // assign to n after dividing by 5
                // n /= 5;
            }        
            return result;
        }
    }
    

  • 0
    Y

    @dreambig You are right. But I'm not sure if writing everything in one line makes the code harder to read for others.


Log in to reply
 

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