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;
没有评论:
发表评论