10212 - The Last Non-zero Digit.

All about problems in Volume 102. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10212 - The Last Non-zero Digit.

Post by yatsen » Tue Sep 10, 2002 9:32 am

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

Post by Pedrinho UFPE » Thu Sep 19, 2002 12:58 am

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 :D


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

Post by Krzysztof Sikora » Sat Sep 21, 2002 9:57 am

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
Location: BANGLADESH
Contact:

Post by Jalal » Wed Oct 02, 2002 8:50 am

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.
:wink:

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

Post by yatsen » Wed Oct 02, 2002 3:08 pm

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

Post by Red Scorpion » Sat Dec 14, 2002 5:34 am

[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. :x [/code]

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

Post by Andrey Mokhov » Sat Dec 14, 2002 7:25 am

You know your algorithm is much like mine, but I managed to get AC in 9.650 sec. :wink:

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. :oops:

Good luck!

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Problem 10212

Post by Red Scorpion » Mon Dec 16, 2002 8:24 am

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. :x

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

Post by Andrey Mokhov » Mon Dec 16, 2002 9:01 am

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: 832
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Mon Dec 16, 2002 9:50 am

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

Post by Andrey Mokhov » Mon Dec 16, 2002 10:29 am

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: 832
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Mon Dec 16, 2002 12:59 pm

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
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan

Post by Andrey Mokhov » Thu Dec 19, 2002 12:25 pm

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... :wink:

Good luck!

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

Post by Dominik Michniewski » Fri Dec 20, 2002 10:31 am

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

Post by Red Scorpion » Wed Jan 08, 2003 8:16 am

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. :lol:

Post Reply

Return to “Volume 102 (10200-10299)”