10212 - The Last Non-zero Digit.

[yatsen]

Can anyone tell me how to solve this problem?

[Pedrinho UFPE]

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

[Krzysztof Sikora]

Let l = length of N = O(log(N))
The complexity of this your algorithm is O(N) = O(10^l).

[Jalal]

U have to solve it like 568
first take a array from the 1st input to 2nd input
then find the co-factors of the primes of every number
of the 1st and second input then multiply them and find
mod of ten and remember to reduce the no. of co-factors
of 5 from the co-factors of 2.

[yatsen]

I try very hard to figure out what you said in the previous post.
I got some idea from that, but I am not very sure what I think is the same as you. Thanks any way, I got AC in 9.10 seconds. Now my question is that somebody solve this 10212 so quickly (less than 1 second). How to do?

[Red Scorpion]

[size=24][/size]
I don't know how to solve this problem without time limit.

My algorithm is :
last = 1;

1. for (k=n-m+1; k<=n; k++)
----- find the count of factor 2 and factor 5;
2. for (k=n-m+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]

[Andrey Mokhov]

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!

[Red Scorpion]

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.

[Andrey Mokhov]

First you count last without factors 2 and 5. Then after the main loop you start loop from 1 to count2-count5 and multiply last by 2 in it. That's enough. And only one BIG loop.

Try it and get AC.

[Dominik Michniewski]

I use following algorithm and got WA in less then 1 sec .... Could anyone tell me why ?

we could calculate value of expression N!/(N-M)! (isn't it ? )
1. factorize N! - when it's done, I got N! in form 2^a*3^b.....
2. factorize (N-M)! - 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

[Andrey Mokhov]

Too little information. Give me your implementation if step 5 - I'll try to think it over and help if I find some bug.

[Dominik Michniewski]

When I come back to home from work, I send you my implementation of this problem ... maybe I made something wrong

Regadrs
Dominik

[Andrey Mokhov]

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!

[Dominik Michniewski]

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

[Red Scorpion]

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 n-m+1 to n(inclusive) and multiply last by 2 or 5.

As in:

count2= 0; count5=0; last=1;
for (i=n-m+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.