b*********n
发帖数: 1258 | 1 Write code for finding number of zeros in n!
OR
Find the first non-zero digit from the right in 100! (Factorial of hundred).
Can an int store hundred factorial. What size of array should be sufficient
to solve the above problem. Write a code for the same.
大家有什么idea? |
g*******y
发帖数: 1930 | 2 1. 找trailing '0's：
while(n/=5) ans1+=n; //find trailing zeros;
2. 找右边数第一个非0数字：
for(i=2;i<=100;i++){
ans2*=i;
while(!(ans2%5)) ans2/=5;
while(!(ans2%2) && ans1){
ans2/=2; ans1--;
}
while(ans2>=10) ans2%=10; //ans2 is a single,non-zero digit
}
1b. 找所有的0:
const int N = 250;
char arr[N];
memset(arr,0,N); arr[0] = 1; //Big endian
for(int i=2;i<=100;i++){
char carry=0;
for(int j=0;j!=N;j+=2){
int temp = i*(arr[j+1]*10+arr[j])+carry;
arr[j] = temp%10;
arr[j+1] = temp%100/10;
carry =temp/100;
}
}
int |
f*********r
发帖数: 68 | 3 呵呵, 这题没有这么简单.
google的面试怎么总是copy人家的题目, 没有一点儿原创性
【在 g*******y 的大作中提到】
: 1. 找trailing '0's：
: while(n/=5) ans1+=n; //find trailing zeros;
: 2. 找右边数第一个非0数字：
: for(i=2;i<=100;i++){
: ans2*=i;
: while(!(ans2%5)) ans2/=5;
: while(!(ans2%2) && ans1){
: ans2/=2; ans1--;
: }
: while(ans2>=10) ans2%=10; //ans2 is a single,non-zero digit
|
g*******y
发帖数: 1930 | 4 哦，经提醒才发现第一个是我没看清题，呵呵
难道只有用数组实现大数乘法了?
用sterling公示，100! 大概就是 e^(100ln100－100)的级别。size随便掏个计算器好了。然后写个大数乘法就搞定了吧。反正每次就乘以最多两位数。。。这个是很容易的。不过我就是还在想，有没更好的方法。不过貌似数中间出现的间断的'0'挺有随机性的。。。
第二题有问题吗?
【在 f*********r 的大作中提到】
: 呵呵, 这题没有这么简单.
: google的面试怎么总是copy人家的题目, 没有一点儿原创性
|
b*********n
发帖数: 1258 | 5 我在网上看的答案都和你的差不多
但是好像不对呀
比如说第一个问题 4!=24
应该没有0,所以输出是0
但是你的算法输出的是4
难道是我理解错了?
【在 g*******y 的大作中提到】
: 哦，经提醒才发现第一个是我没看清题，呵呵
: 难道只有用数组实现大数乘法了?
: 用sterling公示，100! 大概就是 e^(100ln100－100)的级别。size随便掏个计算器好了。然后写个大数乘法就搞定了吧。反正每次就乘以最多两位数。。。这个是很容易的。不过我就是还在想，有没更好的方法。不过貌似数中间出现的间断的'0'挺有随机性的。。。
: 第二题有问题吗?
|
b*********n
发帖数: 1258 | 6 你知道这道题的答案吗？
【在 f*********r 的大作中提到】
: 呵呵, 这题没有这么简单.
: google的面试怎么总是copy人家的题目, 没有一点儿原创性
|
f*********r
发帖数: 68 | 7 我认为第一题如果是Write code for finding number of zeros in n!的话, 只能用大
数乘法. 不过我估计楼主写错了, 应改是Write code for finding number of
trailing zeros in n!, 这样就简单多了.
第二个问题你的算法会溢出, 而且太耗时, 我记得好像可以用一些数论的结论. 我要想
一想先.
【在 g*******y 的大作中提到】
: 哦，经提醒才发现第一个是我没看清题，呵呵
: 难道只有用数组实现大数乘法了?
: 用sterling公示，100! 大概就是 e^(100ln100－100)的级别。size随便掏个计算器好了。然后写个大数乘法就搞定了吧。反正每次就乘以最多两位数。。。这个是很容易的。不过我就是还在想，有没更好的方法。不过貌似数中间出现的间断的'0'挺有随机性的。。。
: 第二题有问题吗?
|
r****o
发帖数: 1950 | 8 6!=720
【在 b*********n 的大作中提到】
: 我在网上看的答案都和你的差不多
: 但是好像不对呀
: 比如说第一个问题 4!=24
: 应该没有0,所以输出是0
: 但是你的算法输出的是4
: 难道是我理解错了?
|
r****o
发帖数: 1950 | 9 谁能举个n!中间有0(non-trailing zero)的例子?
【在 f*********r 的大作中提到】
: 我认为第一题如果是Write code for finding number of zeros in n!的话, 只能用大
: 数乘法. 不过我估计楼主写错了, 应改是Write code for finding number of
: trailing zeros in n!, 这样就简单多了.
: 第二个问题你的算法会溢出, 而且太耗时, 我记得好像可以用一些数论的结论. 我要想
: 一想先.
|
N*D
发帖数: 3641 | 10 http://www.pagalguy.com/forum/quantitative-questions-and-answers/20789-findi
ng-number-zeros-factorial-number.html
这TMD那是靠CS呀，这是靠数学，古狗真TMD无聊。
【在 b*********n 的大作中提到】
: 你知道这道题的答案吗？
|
|
|
g*******y
发帖数: 1930 | 11 我改了，最后一句，改成while(ans2>=10) ans2%=10;
就不会溢出了。
【在 f*********r 的大作中提到】
: 我认为第一题如果是Write code for finding number of zeros in n!的话, 只能用大
: 数乘法. 不过我估计楼主写错了, 应改是Write code for finding number of
: trailing zeros in n!, 这样就简单多了.
: 第二个问题你的算法会溢出, 而且太耗时, 我记得好像可以用一些数论的结论. 我要想
: 一想先.
|
f*********r
发帖数: 68 | 12 factorial(1:10)
ans =
1 2 6 24 120 720
5040 40320 362880 3628800
【在 r****o 的大作中提到】
: 谁能举个n!中间有0(non-trailing zero)的例子?
|
f*********r
发帖数: 68 | 13 你这个第一个也不对吧, find trailing zeros, 应该是 while(n/=5) {ans1++;}
【在 g*******y 的大作中提到】
: 我改了，最后一句，改成while(ans2>=10) ans2%=10;
: 就不会溢出了。
|
g*******y
发帖数: 1930 | 14 不光是trailing '0'而是找所有的0的话，第一个好歹还可以考考数组实现大数乘法；
【在 N*D 的大作中提到】
: http://www.pagalguy.com/forum/quantitative-questions-and-answers/20789-findi
: ng-number-zeros-factorial-number.html
: 这TMD那是靠CS呀，这是靠数学，古狗真TMD无聊。
|
g*******y
发帖数: 1930 | 15 是对的。你想想呢
【在 f*********r 的大作中提到】
: 你这个第一个也不对吧, find trailing zeros, 应该是 while(n/=5) {ans1++;}
|
N*D
发帖数: 3641 | 16 这有啥好考的，现在都64-bit了，以前的大树现在都是小树了
【在 g*******y 的大作中提到】
: 不光是trailing '0'而是找所有的0的话，第一个好歹还可以考考数组实现大数乘法；
|
f*********r
发帖数: 68 | 17 你是对的, 我想错了.
【在 g*******y 的大作中提到】
: 是对的。你想想呢
|
g*******y
发帖数: 1930 | 18 你看看我前面回复里面用sterling公式给出的估计呢，64bit绝对不够。
【在 N*D 的大作中提到】
: 这有啥好考的，现在都64-bit了，以前的大树现在都是小树了
|
f*********r
发帖数: 68 | 19 有问题的不是1, 是2
first non-zero digit应该是2, 4, 6, 8. 你的这个结果会是回是奇数, 你可以随便计
算几个10!, 11!.. 估计就能发现bug了
【在 g*******y 的大作中提到】
: 你看看我前面回复里面用sterling公式给出的估计呢，64bit绝对不够。
|
N*D
发帖数: 3641 | 20 不用看俺也知道2^64 < 100!，这不是point，俺觉得狗狗的interviewer就是以折腾人为
乐。
【在 g*******y 的大作中提到】
: 你看看我前面回复里面用sterling公式给出的估计呢，64bit绝对不够。
|
|
|
g*******y
发帖数: 1930 | 21 我试了几次都是偶数，你是不是测试的是前几分钟还没有修改好的code？
贴一个完整的吧:
int main(){
int i,n,ans1=0,ans2=1;
cin>>n;
int temp=n;
while(temp/=5) ans1+=temp;
for(i=2;i<=n;i++){
ans2*=i;
while(!(ans2%5)) ans2/=5;
while(!(ans2%2) && ans1){
ans2/=2; ans1--;
}
while(ans2>=10) ans2%=10;
}
}
【在 f*********r 的大作中提到】
: 有问题的不是1, 是2
: first non-zero digit应该是2, 4, 6, 8. 你的这个结果会是回是奇数, 你可以随便计
: 算几个10!, 11!.. 估计就能发现bug了
|
b*********n
发帖数: 1258 | 22 is it for trailing zeros or all zeros?
which variable is your output result?
便计
【在 g*******y 的大作中提到】
: 我试了几次都是偶数，你是不是测试的是前几分钟还没有修改好的code？
: 贴一个完整的吧:
: int main(){
: int i,n,ans1=0,ans2=1;
: cin>>n;
: int temp=n;
: while(temp/=5) ans1+=temp;
: for(i=2;i<=n;i++){
: ans2*=i;
: while(!(ans2%5)) ans2/=5;
|
N*D
发帖数: 3641 | 23 all zeros, see my link
【在 b*********n 的大作中提到】
: is it for trailing zeros or all zeros?
: which variable is your output result?
:
: 便计
|
g*******y
发帖数: 1930 | 24 ans1: trailing zeros
ans2: first non-zero digit (from right)
所有的zeros我打算试着写个练练~（code贴在2楼），答案是30个0，不知道对不对?
【在 b*********n 的大作中提到】
: is it for trailing zeros or all zeros?
: which variable is your output result?
:
: 便计
|
f*********r
发帖数: 68 | 25 这个O(N)方法是对的. 不过估计不是google想要的算法.
【在 g*******y 的大作中提到】
: 我试了几次都是偶数，你是不是测试的是前几分钟还没有修改好的code？
: 贴一个完整的吧:
: int main(){
: int i,n,ans1=0,ans2=1;
: cin>>n;
: int temp=n;
: while(temp/=5) ans1+=temp;
: for(i=2;i<=n;i++){
: ans2*=i;
: while(!(ans2%5)) ans2/=5;
|
h*******e
发帖数: 225 | 26 Read the stuff and see if works like that before you post
【在 N*D 的大作中提到】
: all zeros, see my link
|
b*********n
发帖数: 1258 | 27 yes, now i can see you are right.
便计
【在 g*******y 的大作中提到】
: 我试了几次都是偶数，你是不是测试的是前几分钟还没有修改好的code？
: 贴一个完整的吧:
: int main(){
: int i,n,ans1=0,ans2=1;
: cin>>n;
: int temp=n;
: while(temp/=5) ans1+=temp;
: for(i=2;i<=n;i++){
: ans2*=i;
: while(!(ans2%5)) ans2/=5;
|
f*********r
发帖数: 68 | 28 写了一个O(log5(N))的算法, 不过好像还有更快的!
int n;
int tbl[] = {1, 1, 2, 6, 4, 4, 4, 8, 4, 6};
int tbl2[][4] = {{}, {2, 6, 8, 4}, {4, 2, 6, 8}, {6, 8, 4, 2}, {8, 4, 2, 6}};
int fun(int n) {
if(n<5) return tbl[n];
int k = (fun(n/5)*tbl[n%10]*6)%10;
return tbl2[k/2][(n/5)%4];
}
void solve() {
int res;
res = fun(n);
cout<
}
int main(){
freopen("in.txt", "r", stdin);
while(cin>>n) {
solve();
}
} |
f********y
发帖数: 69 | 29 (1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10)
2 * 5 = 0, 10 = 10
(1* 3 * 4 * 6 * 7 * 8 * 9) 的结果乘上10次
即8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8
最后一位为4 |
f********y
发帖数: 69 | 30 (1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10)
2 * 5 = 0, 10 = 10
(1* 3 * 4 * 6 * 7 * 8 * 9) 的结果乘上10次
即8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8
最后一位为4 |
|
|
t****t
发帖数: 6806 | 31 你这个回答未免也太不动脑了, 自己拿个计算器算算
21*22*...*30最后一位非0是多少
【在 f********y 的大作中提到】
: (1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10)
: 2 * 5 = 0, 10 = 10
: (1* 3 * 4 * 6 * 7 * 8 * 9) 的结果乘上10次
: 即8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8
: 最后一位为4
|
f********y
发帖数: 69 | 32 (1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10)
2 * 5 = 0, 10 = 10
(1* 3 * 4 * 6 * 7 * 8 * 9) 的结果乘上10次
即8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8
最后一位为4 |
f********y
发帖数: 69 | 33 (1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10)
2 * 5 = 0, 10 = 10
(1* 3 * 4 * 6 * 7 * 8 * 9) 的结果乘上10次
即8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8
最后一位为4 |
f********y
发帖数: 69 | 34 (1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10)
2 * 5 = 0, 10 = 10
(1* 3 * 4 * 6 * 7 * 8 * 9) 的结果乘上10次
即8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8
最后一位为4
人为
【在 N*D 的大作中提到】
: 不用看俺也知道2^64 < 100!，这不是point，俺觉得狗狗的interviewer就是以折腾人为
: 乐。
|
t****t
发帖数: 6806 | 35 kao, 没脑的答案还要连发5遍! 这什么世道.
【在 f********y 的大作中提到】
: (1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10)
: 2 * 5 = 0, 10 = 10
: (1* 3 * 4 * 6 * 7 * 8 * 9) 的结果乘上10次
: 即8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8
: 最后一位为4
:
: 人为
|
N******e
发帖数: 437 | 36 同学给解释一下吧。
中间的那些0是怎么造成的呢？
【在 g*******y 的大作中提到】
: 我试了几次都是偶数，你是不是测试的是前几分钟还没有修改好的code？
: 贴一个完整的吧:
: int main(){
: int i,n,ans1=0,ans2=1;
: cin>>n;
: int temp=n;
: while(temp/=5) ans1+=temp;
: for(i=2;i<=n;i++){
: ans2*=i;
: while(!(ans2%5)) ans2/=5;
|
M*****a
发帖数: 2054 | 37 simple
find 2因子，find 5因子的个数
小学竞赛题
).
sufficient
【在 b*********n 的大作中提到】
: Write code for finding number of zeros in n!
: OR
: Find the first non-zero digit from the right in 100! (Factorial of hundred).
: Can an int store hundred factorial. What size of array should be sufficient
: to solve the above problem. Write a code for the same.
: 大家有什么idea?
|
m********0
发帖数: 2717 | 38 not at all。
不是算tailing zeros，算所有零的个数。
自己看清楚题目和回帖再发贴吧。
【在 M*****a 的大作中提到】
: simple
: find 2因子，find 5因子的个数
: 小学竞赛题
:
: ).
: sufficient
|
m********0
发帖数: 2717 | 39 你自己错了。人家算的没错。本来就是4。
100！第一个非零的就是4。
【在 t****t 的大作中提到】
: kao, 没脑的答案还要连发5遍! 这什么世道.
|
g*******y
发帖数: 1930 | 40 那是碰巧碰对的，你用他的方法算算30!试试呢。
【在 m********0 的大作中提到】
: 你自己错了。人家算的没错。本来就是4。
: 100！第一个非零的就是4。
|
|
|
m********0
发帖数: 2717 | 41 恩。sorry。我只看了结果，我检讨。。
【在 g*******y 的大作中提到】
: 那是碰巧碰对的，你用他的方法算算30!试试呢。
|
m********0
发帖数: 2717 | 42 算一共多少个零的问题，有人提供code吗？non-trivial的非大数乘法的code。
虽然很多任意范围，任意精度的库很多了。 |
t****t
发帖数: 6806 | 43 我不认为中间的零可以随意的计算出来.
【在 m********0 的大作中提到】
: 算一共多少个零的问题，有人提供code吗？non-trivial的非大数乘法的code。
: 虽然很多任意范围，任意精度的库很多了。
|
