10212  The Last Nonzero Digit.
Moderator: Board moderators
10212  The Last Nonzero Digit.
Can anyone tell me how to solve this problem?

 New poster
 Posts: 15
 Joined: Tue Sep 10, 2002 1:56 am
 Location: Brasil
 Contact:
10212  the problem of an O(n) solution
I have a problem with the complexity of my algorithm to solve this problem.
let pick N and M, with N >= M
if we do:
[cpp]
unsigned long i, k = 1;
for(i=M+1;i<=N;i++) {
k = k * i;
takeTheZerosFrom(k);
takeTheGoodPartOf(k);
} printf("%u\n",lastDigitOf(k));
[/cpp]
it produces the right solution.
takeTheZerosFrom's functionality the name tells
takeTheGoodPartOf take the k and let k with the last 7 numbers of k
ex: k = 2355356200
after doing takeTheZerosFrom we have
k = 23553562
after doing takeTheGoodPartOf(k) we have
k = 3223562
The problem with this algorithm is that the complexity is O(N)
and it is sure that it's a TLS...
How can we improve this complexity??
Thanks in advance,
Pedro Machado
I tried to solve this problem with the basic idea of taking the k  las digits of the
let pick N and M, with N >= M
if we do:
[cpp]
unsigned long i, k = 1;
for(i=M+1;i<=N;i++) {
k = k * i;
takeTheZerosFrom(k);
takeTheGoodPartOf(k);
} printf("%u\n",lastDigitOf(k));
[/cpp]
it produces the right solution.
takeTheZerosFrom's functionality the name tells
takeTheGoodPartOf take the k and let k with the last 7 numbers of k
ex: k = 2355356200
after doing takeTheZerosFrom we have
k = 23553562
after doing takeTheGoodPartOf(k) we have
k = 3223562
The problem with this algorithm is that the complexity is O(N)
and it is sure that it's a TLS...
How can we improve this complexity??
Thanks in advance,
Pedro Machado
I tried to solve this problem with the basic idea of taking the k  las digits of the
Interested

 New poster
 Posts: 11
 Joined: Mon Sep 02, 2002 4:40 pm
 Location: Poland

 Experienced poster
 Posts: 192
 Joined: Sat Nov 30, 2002 5:14 am
10212  The Last Non Zero Digit
[size=24][/size]
I don't know how to solve this problem without time limit.
My algorithm is :
last = 1;
1. for (k=nm+1; k<=n; k++)
 find the count of factor 2 and factor 5;
2. for (k=nm+1; k<=n; k++) {
 while (!(k%5) && count_5>0) { k/=5; count_5; }
 while (!(k%2) && count_2>0) (k/=2; count_2; }
last = multiply (k, last);
last = last digit of variable 'last';
}
3. print last;
for n<=1000000 && m<= 1000000 my code run fast enough,
but for n = 20000000 and m = 20000000 my code stuck here.
if anyone have time, please help me .
Thanks. [/code]
I don't know how to solve this problem without time limit.
My algorithm is :
last = 1;
1. for (k=nm+1; k<=n; k++)
 find the count of factor 2 and factor 5;
2. for (k=nm+1; k<=n; k++) {
 while (!(k%5) && count_5>0) { k/=5; count_5; }
 while (!(k%2) && count_2>0) (k/=2; count_2; }
last = multiply (k, last);
last = last digit of variable 'last';
}
3. print last;
for n<=1000000 && m<= 1000000 my code run fast enough,
but for n = 20000000 and m = 20000000 my code stuck here.
if anyone have time, please help me .
Thanks. [/code]

 Experienced poster
 Posts: 128
 Joined: Fri Nov 15, 2002 7:45 am
 Location: Kyrgyzstan
You know your algorithm is much like mine, but I managed to get AC in 9.650 sec.
Try to optimize your code a bit  do everything in one loop.
P.S. The problem can be solved faster, but when I coded it I was lazy enough and I didn't want to optimize it although I was almost the last in the ranklist.
Good luck!
Try to optimize your code a bit  do everything in one loop.
P.S. The problem can be solved faster, but when I coded it I was lazy enough and I didn't want to optimize it although I was almost the last in the ranklist.
Good luck!

 Experienced poster
 Posts: 192
 Joined: Sat Nov 30, 2002 5:14 am
Problem 10212
What do tou mean by :
"Do Everything in one loop ?"
How can I know the number that must be divided by two or by five, if I count the factor of two and five in one loop ?
Please Help me ....
Thanks.
"Do Everything in one loop ?"
How can I know the number that must be divided by two or by five, if I count the factor of two and five in one loop ?
Please Help me ....
Thanks.

 Experienced poster
 Posts: 128
 Joined: Fri Nov 15, 2002 7:45 am
 Location: Kyrgyzstan

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
I use following algorithm and got WA in less then 1 sec .... Could anyone tell me why ?
we could calculate value of expression N!/(NM)! (isn't it ? )
1. factorize N!  when it's done, I got N! in form 2^a*3^b.....
2. factorize (NM)!  I got the same form ....
3. substract powers: from powers of (1) substract powers of (2)
4. substract power of 2 with power of 5 ....
5. calculate last digit, knowing that powers of 2 are ending with 1,2,4,8,6,2,4 ... and so on for 3,7,9and 1 ....
6. print last digit ....
Could anyone help me ?
Regards
Dominik
we could calculate value of expression N!/(NM)! (isn't it ? )
1. factorize N!  when it's done, I got N! in form 2^a*3^b.....
2. factorize (NM)!  I got the same form ....
3. substract powers: from powers of (1) substract powers of (2)
4. substract power of 2 with power of 5 ....
5. calculate last digit, knowing that powers of 2 are ending with 1,2,4,8,6,2,4 ... and so on for 3,7,9and 1 ....
6. print last digit ....
Could anyone help me ?
Regards
Dominik

 Experienced poster
 Posts: 128
 Joined: Fri Nov 15, 2002 7:45 am
 Location: Kyrgyzstan

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:

 Experienced poster
 Posts: 128
 Joined: Fri Nov 15, 2002 7:45 am
 Location: Kyrgyzstan
Dominik, I found a bug in your code. You use primes till sqrt(20000000), but that's wrong. Your algorithm requires primes till 20000000 as N! can contain prime factors up to N. For example your program for N=7777 and M=234 gives answer 4 but the correct answer is 2.
Anyway your algorithm is quite interesting. It would be even fantastic if sqrt(N) were enough...
Good luck!
Anyway your algorithm is quite interesting. It would be even fantastic if sqrt(N) were enough...
Good luck!

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
When I wiat for your answer, I modify my code i this way, that I calculate all primes not to 5000, but to 20000000 (max N in problem) ... My program run about 5,4 sec , but still WA ... I check your input as soon as possible ... maybe I found another bug ....
But thank you very much for your help )
Dominik
But thank you very much for your help )
Dominik

 Experienced poster
 Posts: 192
 Joined: Sat Nov 30, 2002 5:14 am
P 10212
Well, I have try to solve this Problem for a month, but I still got Time Limit.
I have change my algo (first I count last without factor 2 and factor 5),
and after that i start loop from nm+1 to n(inclusive) and multiply last by 2 or 5.
As in:
count2= 0; count5=0; last=1;
for (i=nm+1; i<=n; i++) {
 tp = i;
 while (!(tp%10)) tp/=10;
 while (!(tp%2)) {
 tp/=2;
 count2++;
 }
 while (!(tp%5)) {
 tp/=5;
 count5++;
 }
tp = lastdigit(tp);
last *= tp;
last = lastdigit(last);
}
if (count2 >= count5) {
 for (i=count5+1; i<=count2; i++) {
last *=2;
last = lastdigit(last);
}
}
else {
 for (i=count2+1; i<=count5; i++) {
last*=5;
lastdigit(last);
}
}
printf ("%d\n", last);

Please Help me ...
Thanks.
I have change my algo (first I count last without factor 2 and factor 5),
and after that i start loop from nm+1 to n(inclusive) and multiply last by 2 or 5.
As in:
count2= 0; count5=0; last=1;
for (i=nm+1; i<=n; i++) {
 tp = i;
 while (!(tp%10)) tp/=10;
 while (!(tp%2)) {
 tp/=2;
 count2++;
 }
 while (!(tp%5)) {
 tp/=5;
 count5++;
 }
tp = lastdigit(tp);
last *= tp;
last = lastdigit(last);
}
if (count2 >= count5) {
 for (i=count5+1; i<=count2; i++) {
last *=2;
last = lastdigit(last);
}
}
else {
 for (i=count2+1; i<=count5; i++) {
last*=5;
lastdigit(last);
}
}
printf ("%d\n", last);

Please Help me ...
Thanks.