## 10212 - The Last Non-zero Digit.

Moderator: Board moderators

yatsen
Learning poster
Posts: 68
Joined: Fri Nov 23, 2001 2:00 am
Location: taiwan

### 10212 - The Last Non-zero Digit.

Can anyone tell me how to solve this problem?

Pedrinho UFPE
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??

Pedro Machado I tried to solve this problem with the basic idea of taking the k - las digits of the
Interested

Krzysztof Sikora
New poster
Posts: 11
Joined: Mon Sep 02, 2002 4:40 pm
Location: Poland
Let l = length of N = O(log(N))
The complexity of this your algorithm is O(N) = O(10^l). -- Krzysztof Sikora

Jalal
Learning poster
Posts: 65
Joined: Sun Jun 02, 2002 8:41 pm
Contact:
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
Learning poster
Posts: 68
Joined: Fri Nov 23, 2001 2:00 am
Location: taiwan
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
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=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.

Thanks. [/code]

Andrey Mokhov
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!

Red Scorpion
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 ?

Thanks. Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan
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
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!/(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
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan
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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
When I come back to home from work, I send you my implementation of this problem ... maybe I made something wrong Dominik

Andrey Mokhov
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!

Dominik Michniewski
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

Red Scorpion
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 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);
------------------------------------------------------
Thanks. 