Factorial Trailing Zeroes (Divide-and-Conquer)
5169 ワード
QUESTION
Given an integer n, return the number of trailing zeroes in n!.
Note: Your solution should be in logarithmic time complexity.
FIRST TRY
Result: Time Limit Exceeded
Last executed input: 0
SECOND TRY
n=0を考慮した場合
Result: Time Limit Exceeded
Last executed input:1808548329
THIRD TRY
2は5より多いに違いない
注意しなければならないのは25ということです.5と5を乗算した結果です.だから、n/5の中に何個の5があるかを見なければなりません.つまり、nの中に何個の25があるか、125625があるかを見ることに相当します.
Result: Accepted
Given an integer n, return the number of trailing zeroes in n!.
Note: Your solution should be in logarithmic time complexity.
FIRST TRY
class Solution {
public:
int trailingZeroes(int n) {
int divident;
int nOf2 = 0;
int nOf5 = 0;
while(n%2 == 0)
{
nOf2++;
divident = n/2;
}
while(n%5 == 0)
{
nOf5++;
divident = n/5;
}
return min(nOf2,nOf5);
}
};
Result: Time Limit Exceeded
Last executed input: 0
SECOND TRY
n=0を考慮した場合
class Solution {
public:
int trailingZeroes(int n) {
int divident;
int nOf2 = 0;
int nOf5 = 0;
for(int i = 1; i < n; i++)
{
divident = i;
while(divident%2 == 0)
{
nOf2++;
divident /= 2;
}
divident = i;
while(divident%5 == 0)
{
nOf5++;
divident /= 5;
}
}
return min(nOf2,nOf5);
}
};
Result: Time Limit Exceeded
Last executed input:1808548329
THIRD TRY
2は5より多いに違いない
注意しなければならないのは25ということです.5と5を乗算した結果です.だから、n/5の中に何個の5があるかを見なければなりません.つまり、nの中に何個の25があるか、125625があるかを見ることに相当します.
class Solution {
public:
int trailingZeroes(int n) {
if(n==0) return 0;
int divident=n;
int nOf5 = 0;
while(divident!= 0)
{
divident /= 5;
nOf5+=divident;
}
return nOf5;
}
};
Result: Accepted