Zero after factorial [leetcode-172]

Topic describes

Thought analysis

Every 0 at the end of a base 10 number indicates the presence of a factor 10, as in any base M number, adding an extra 0 to the end is equivalent to multiplying by M. 10 factorizes into 2 × 5 — so only the prime numbers 2 multiplied by 5 produce 0. No other two prime numbers multiplied by each other produce 0, and 2 multiplied by 5 produces only one 0. Therefore, there are as many 0’s as there are (2,5) pairs in the whole factorization, and there are obviously more than 5’s in the factorization, so there are as many (2,5) pairs as there are 5’s. So, talking about how many zeros there are at the end of a factorial of a number, that translates to the question of how many fives there are in the prime factorization of all of these numbers from 1 to n.

1. Every 5, there will be a 0, such as 5, 10, 15,20… 2. Every 5×5 will produce a 0, such as 25,50,75,100. Because 25, 50 is 5 times 5 times x, so we have two 5’s, so we have one more 5, and the same thing. 3. Every 5×5×5 there’s another 0, like 125,250…

So 100! How many zeros are there at the end: 100/5+100/25=20+4=24 then 1000! How many zeros do we have at the end? Similarly: 1000/5+1000/25+1000/125=200+40+8=248

Code implementation

class Solution {
public:
    int trailingZeroes(int n) {
        int ret =0;
        while(n)
        {
            ret += n/5;
            n /= 5;
        }
        returnret; }};Copy the code