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

ezaztime
New poster
Posts: 1
Joined: Wed Feb 06, 2008 10:53 pm
Location: BGD-DHK
Contact:

10212 CE

Post by ezaztime » Wed Feb 06, 2008 11:06 pm

Code: Select all

int main()
{
	//freopen("10212.in","r",stdin);
	unsigned n,m;
	while(cin>>n && cin>>m)
	{
		unsigned int f1=n;
		if(f1==0)
			f1=1;
		for(unsigned int i=1;i<n;i++)
		{
			f1=f1*i;
		}
		unsigned int f2=n-m;
		if(f2==0)
			f2=1;

		for(i=1;i<n-m;i++)
		{
			f2=f2*i;
		}
		unsigned int f=f1/f2;		
		if(f%10!=0)
		{
			f=f%10;
		}
		else
		{
			while(f%10==0)
			{
				f=f/10;
			} 
			f=f%10;
		}
		cout<<"f : "<<f<<endl;
	}
	return 0;
}
it gives the correct result when i myself test it ...

any body please help to find out the bug...
Last edited by brianfry713 on Thu Nov 20, 2014 9:08 pm, edited 1 time in total.
Reason: Added code blocks

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:

Post by sapnil » Tue Feb 12, 2008 10:19 pm

Code: Select all

for(unsigned int i=1;i<n;i++) 
{ 
f1=f1*i; 
}
Here you find n!, but n<=20000000

>> Hope it help

Thanks
Keep posting
Sapnil
"Dream Is The Key To Success"

@@@ Jony @@@

iggy
New poster
Posts: 3
Joined: Mon May 05, 2008 10:44 am

Re: 10212 - The Last Non Zero Digit

Post by iggy » Mon May 05, 2008 2:21 pm

I still wonder how people get this calculated in under 0.002s..

What worked for me was to first cache pairs (c, d) for every x: 1..20'000'000 such that
x = 2^a * 5^b * r;
c = a - b; // easily calculated
d = r % 10;

Then considering:
if x -> (c, d) then lastnonzerodigit(x) = { d, if c = 0 | 5, if c<0 | (d*2^c) % 10, if c > 0 }
if x -> (c1, d1) and y -> (c2, d2) then x*y -> (c1+c2, (d1*d2) % 10)

And given N and M, we are interested in last non-zero digit of
N*(N-1)*...*(N-M+1) -> (c1 + c2 + ... + cm-1, (d1 * d2 * ... dm-1) % 10)

But this barely makes it in time (9.5s).

I've tried the prime factorization of N! and (N-M)! but didn't fit in time.. What's the trick to calculating this problem fast?

Chirag Chheda
Learning poster
Posts: 74
Joined: Sat Jun 21, 2008 12:24 pm
Location: India

Re: 10212 - The Last Non Zero Digit

Post by Chirag Chheda » Fri Jun 27, 2008 8:34 am

Can someone plz give me test cases so that i can find the bug in my code
Thnx in advance
Last edited by Chirag Chheda on Fri Jun 27, 2008 10:48 am, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 10212 - The Last Non Zero Digit

Post by Jan » Fri Jun 27, 2008 9:02 am

I am asking why it should work?

Code: Select all

b %= 20000000;
Ami ekhono shopno dekhi...
HomePage

Chirag Chheda
Learning poster
Posts: 74
Joined: Sat Jun 21, 2008 12:24 pm
Location: India

Re: 10212 - The Last Non Zero Digit

Post by Chirag Chheda » Fri Jun 27, 2008 10:49 am

ok now i got it
well my approach was completely wrong at it.
I think now i shud give it a try

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Re: 10212 - The Last Non Zero Digit

Post by Sedefcho » Tue Aug 26, 2008 7:20 pm

To iggy:

I also don't know how some people solved this one in less than 0.010 secs
but (if they used a fair algorithm) I guess they tried to generate the numbers
instead of iterating through them. What do I mean? Well...

My algorithm runs in 3.710 secs and is implemented in C++.

Some small hints about it.

1. Each natural number N can be represented as N = (2^a) * (5^b) * r
where GCD(r,2)=1 and GCD(r,5)=1 and a>=0 and b>=0.
Now if you precalculate a,b,r for N=1 to 20 million things get
much simpler. And if you use the cached values calculated above
an O(N-M) algorithm (for each test case) will pass the time limit for sure.

2. Use modular exponentiation which runs in O(log K) where K is the degree.
I mean for example if you want to calculate ( 2 ^ 1000 ) % 10 this can be done
easily in O(log 1000) time.

Even these two simple observations can take your program
to about 3.800 - 4.000 secs runtime for the judge input
(this remark is valid as of August 26, 2008).

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

Re: 10212 - The Last Non Zero Digit

Post by stcheung » Sun Oct 12, 2008 9:08 am

Let me summarize the method to not get TLE:
(1) For each number in the loop (eg. [8, 7, 6] if you are calculating P_8_3), calculate it as 2^a * 5^b * c
(2) Keep a running sum of the a & b above. You can simply use a variable, add a and subtract b from it in each iteration
(3) After you figure out c in each iteration, do c % 10. Keep track of all these c %10. Each this example, you would end up with one 7 and one 3
(4) Multiply all these c % 10 together. I don't mean it literally because that's way too slow. You should be able to quickly calculate the final digit when multiplying say ten thousand 3s together. Observe the last digit pattern 3, 9, 7, 1, 3... Then multiply the effect of the running sum in (2). If there's more 2 than 5, your running sum would be positive and you have to what's the digit for multiplying all these 2 together. Similarly if there's more 5 than 2.
(5) If you only do (1)-(4), there's great chance you still get TLE. In that case, you need to have a cache so you can figure out the running sum and the c % 10 directly. Use byte (or whatever is the smallest integer size in your language) to store these so you won't have OutOfMemory error.

My Java program got AC under 6 sec so if you do all these you should get AC well under the TLE limit.

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 10212 - The Last Non Zero Digit

Post by Shafaet_du » Wed Oct 06, 2010 6:22 pm

sample:

Code: Select all

100 10
200000 34
        453434 23
  5656565 343
546433 2334
   123123 1
45546 934
1 1
122342 12

Code: Select all

2
4
8
8
4
3
4
1
8

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

Re: 10212 - The Last Non Zero Digit

Post by Dominik Michniewski » Sun Mar 27, 2011 1:05 am

Finally I got it solved :):)

I got 4,3s time (in the middle of all users, which solved this problem).
My only mistake was improper handling of integer overflow :(:(:(

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

najim_ju
New poster
Posts: 1
Joined: Wed Apr 27, 2011 10:05 pm

10212 WA after TLE!!!

Post by najim_ju » Wed Apr 27, 2011 10:16 pm

najim_ju wrote:Plz,Help me to figure out why i am getting WA???what is correct or more efficient approach to this problem?<sorry,i m a naive user...so i may not gave the post in correct approach>

Code: Select all

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
#define max 20000100
#define MOD 100000000

int check[max+2];
int prime[max+2];
void generate_prime();

int LND(int b,int p);

int main()
{
generate_prime();
//freopen("inp.txt","r",stdin);
int n,r,k;
while(scanf("%d %d",&n,&r)==2)
	{
	long long int a=1;
	int R=n-r;
	int i=0;
	int ct_n=0,ct_d=0,ct_2n=0,ct_2d=0,ct_5n=0,ct_5d=0;
	int N=n;
	int D=R;
	for(i=0;prime[i]<=n;i++)
		{
		ct_n=0,ct_d=0;
		N=n;
		if(prime[i]<=R)D=R;
		else D=0;
		if(prime[i]!=2 && prime[i]!=5)
			{
			while(N)
				{
				ct_n+=N/prime[i];
				N/=prime[i];
				}
			while(D)
				{
				ct_d+=D/prime[i];
				D/=prime[i];
				}
			ct_n=ct_n-ct_d;
			a=(a*LND(prime[i],ct_n))%MOD;
			}
		else if(prime[i]==2)
			{
			while(N)
				{
				ct_2n+=N/prime[i];
				N/=prime[i];
				}
			while(D)
				{
				ct_2d+=D/prime[i];
				D/=prime[i];
				}
			ct_2n=ct_2n-ct_2d;
			}
		else if(prime[i]==5)
			{
			while(N)
				{
				ct_5n+=N/prime[i];
				N/=prime[i];
				}
			while(D)
				{
				ct_5d+=D/prime[i];
				D/=prime[i];
				}
			ct_5n=ct_5n-ct_5d;
			ct_2n=ct_2n-ct_5n;
			ct_5n=0;
			a=(a*LND(2,ct_2n))%MOD;
			}
		//i++;
		}
	printf("%d\n",a%10);
	}
return 0;
}

void generate_prime()
{
long i,j,c=0;
for(i=2;i<=max;i++) check[i]=1;
for(i=2;i<=sqrt(max);  )
	{
	for(j=i+i;j<=max;j+=i)check[j]=0;
	i++;
	for( ;!check[i];i++);
	}
j=0;
for(i=2;i<max;i++) 
	{
	if(check[i]==1)prime[j++]=i;
	}
}

int LND(int b,int p)
{
b=b%10;
if(p==0)return 1;
else if(p%4==1)return b;
else if(p%4==2)return (b*b)%10;
else if(p%4==3)return (b*b*b)%10;
else if(p%4==0)return (b*b*b*b)%10;
}
Last edited by brianfry713 on Thu Nov 20, 2014 9:09 pm, edited 1 time in total.
Reason: Added code blocks

User avatar
plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

Re: 10212 - The Last Non Zero Digit

Post by plamplam » Sat Sep 10, 2011 11:04 pm

I am yet to get Accepted in this problem-.- :oops: I tested my code with several large random numbers and compared my output against uvatoolkit. I handled cases where n or m is 0 and although my brute force algorithm sucks, it should not, by any means, get Wrong Answer. Okay enough yelling, here are some randomly generated inputs which I used. The outputs are from uvatoolkit:

Code: Select all

2727310 169580
8410985 7364225
8717510 8305150
8945955 462075
3639260 575840
7979410 7261440
8712325 2794105
1290455 520940
7459080 2953620
9049655 6955220
7083015 6821020
775920 732000
9607805 6956135
2586400 2221620
8548540 6113725
9082290 1976705
7639335 5434795
7301395 4031185
8308200 7609140
8703480 4603060
6961930 817400
9046300 8192605
9256140 3110085
6224440 2864255
3983910 1580510
8750755 3867400
5557100 4057720
8632415 3843000
9162200 6306790
8079755 1887950
6703900 3342495
8501570 5023045
2784955 2540345
4175145 1521950
3323585 2860290
9673685 8819075
7444745 6355285
7715280 1382870
9452255 2078880
5481155 2113955
5374710 4711030
5205130 3641395
9584320 9373565

Code: Select all

2
6
2
8
4
2
2
4
6
4
6
6
6
2
2
8
8
6
8
4
6
4
4
2
8
2
2
2
6
8
8
4
4
4
8
8
2
2
2
6
2
8
6
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

X123
New poster
Posts: 11
Joined: Fri Oct 04, 2013 1:28 am

Re: 10212 - The Last Non Zero Digit

Post by X123 » Mon Dec 30, 2013 3:03 pm

i solved uva 568 to find out the last non zero digit of n!
and got accepted. here is my code

Code: Select all

#include<stdio.h>
#define max 20000000
#define lmt 4473

unsigned flag[max>>6];

#define ifc(n) (flag[n>>6]&(1<<((n>>1)&31)))
#define isc(n) (flag[n>>6]|=(1<<((n>>1)&31)))
int power(int prime,int n)
{
	int a=n;
int pow=0;
while(a!=0)
{
	pow=a/prime+pow;
	a=a/prime;
}
return pow;
}
int main()
{
	int index[3][4]={{6,2,4,8},{1,3,9,7},{1,7,9,3}};
	int i,j,k,n,twos,fives,digittwo,threes,p,sevens,digitthree,digitseven,lastdigit;
	for(i=3;i<lmt;i+=2)
		if(!ifc(i))
		for(j=i*i,k=i<<1;j<max;j+=k)
		isc(j);
while(scanf("%d",&n)==1)
{
	if(n==0||n==1)
		printf("%5d -> 1\n",n);
else

{
twos=power(2,n);

fives=power(5,n);
twos=(twos-fives)%4;
digittwo=index[0][twos];
threes=power(3,n);
sevens=power(7,n);
for(i=11;i<=n;i+=2){
	if(!ifc(i))
{
	p=i%10;
	int c=power(i,n);
	if(p==7)
		sevens=sevens+c;
	else if(p==3)
		threes=threes+c;
	else if(p==9)
		threes=threes+2*c;
}
}
threes=threes%4;
digitthree=index[1][threes];
sevens=sevens%4;
digitseven=index[2][sevens];

lastdigit=(digittwo*digitseven*digitthree)%10;
printf("%5d -> %d\n",n,lastdigit);

}

}
	return 0;
}
 then i modified this code for 10212. but getting WA.. can anybody help me?  :-? 


#include<stdio.h>
#define max 20000100
#define lmt 4473

unsigned flag[max>>6];

#define ifc(n) (flag[n>>6]&(1<<((n>>1)&31)))
#define isc(n) (flag[n>>6]|=(1<<((n>>1)&31)))
int power(int prime,int n)
{
	int a=n;
int pow=0;
while(a!=0)
{
	pow=a/prime+pow;
	a=a/prime;
}
return pow;
}
int main()
{
	int index[3][4]={{6,2,4,8},{1,3,9,7},{1,7,9,3}};
	int i,j,k,n,twos,fives,digittwo,threes,p,sevens,digitthree,digitseven,lastdigit,u;
	for(i=3;i<lmt;i+=2)
		if(!ifc(i))
		for(j=i*i,k=i<<1;j<max;j+=k)
		isc(j);
while(scanf("%d %d",&n,&u)==2)
{
	if(n==0||n==1||u==0)
		printf("1\n");
		else if(u==1){
				while(n%10==0)
				n=n/10;
			printf("%d\n",n%10);
		}
else
{
	u=n-u;
twos=power(2,n)-power(2,u);

fives=power(5,n)-power(5,u);
twos=(twos-fives)%4;
digittwo=index[0][twos];
threes=0;
sevens=0;
for(i=3;i<=n;i+=2){
	if(!ifc(i))
{
	p=i%10;
	if(p==7||p==3||p==9){
	int c=power(i,n)-power(i,u);
	if(p==7)
		sevens=sevens+c;
	else if(p==3)
		threes=threes+c;
	else if(p==9)
		threes=threes+2*c;
	}
}
}
threes=threes%4;
digitthree=index[1][threes];
sevens=sevens%4;
digitseven=index[2][sevens];
lastdigit=(digittwo*digitseven*digitthree)%10;
printf("%d\n",lastdigit);

}

}
	return 0;
}
Last edited by brianfry713 on Thu Nov 20, 2014 9:08 pm, edited 1 time in total.
Reason: Added code blocks
Many of life’s failures are people who did not realize how close they were to success when they gave up.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10212 - The Last Non Zero Digit

Post by brianfry713 » Wed Jan 15, 2014 1:20 am

Input 7 3, output should be 1
Check input and AC output for thousands of problems on uDebug!

dibery
Learning poster
Posts: 76
Joined: Sat Feb 23, 2013 4:16 pm
Location: Taiwan, Taipei
Contact:

Re: 10212 - The Last Non-zero Digit.

Post by dibery » Thu Nov 20, 2014 7:26 am

Some more cases

Input:
15 1
15 2
15 3
15 4

Output:
5
1
3
6
Life shouldn't be null.

Post Reply

Return to “Volume 102 (10200-10299)”