2015年8月18日星期二

Lintcode: Trailing Zeros


Bad solution:
I tried to get the   factor result at first, and keep reducing trailing zeros when factoring.
When the input is small, it's ok. But when the input is a little larger, things get worse quickly.
return negative or zero or just wrong positive result.


class Solution {
 public:
    // param n : description of n
    // return: description of return 
    long long trailingZeros(long long n) {
        if(n == 0) return 1;
        long long num = 1;
        for(int i =1; i <= n; i++){
            num = num * i;
        }
        int res = 0;
        while(num && !(num % 10) ){
            res++;
            num = num / 10;
        }
        return res;
    }
};

Normal solution:
http://www.danielbit.com/blog/puzzle/leetcode/leetcode-factorial-trailing-zeroes
The key of this problem is to count how many 5 multiples in n. Normally, each 5 multiples can generate one trailing zero. However, when 5 multiples are 25(5^2), 125(5^3)... They can generate 2, 3, ... trailing zeros.
So we can calculate sum 0f n/5 + n/25 + n/125 ... to get the result.

Note: The type of sum and i has to be long long.
Time: O(log5n)
Space: O(1)


class Solution {
 public:
    // param n : description of n
    // return: description of return 
    long long trailingZeros(long long n) {
        long long sum = 0;
        for( long long i = 5; n / i >= 1; i *= 5){
            sum += n / i;
        }
        return sum;
    }
};

condition n /i >= 1 can be changed by n / i > 0 or n >= i

Analysis: http://algorithm.yuanbin.me/math_and_bit_manipulation/factorial_trailing_zeroes.html
1. Should consider exception. If n < 0, return -1;
2. replace i *= 5 by n /= 5;

没有评论:

发表评论