Question->http://www.spoj.com/problems/LASTDIG/
My solution is not accepted on Spoj because my solution is taking
more than 700 bytes.
But i m not getting how to reduce or shorten my code or what can be done
to reduce the memory
usage to be less than 700 bytes.I also read somewhere that by removing
spaces b/w the code source
code memory will reduce but still after doing that my code is not
accepted.Plz help
**
#include<iostream>
using namespace std;
int lastdigit(int a,long int b);
int main()
{
int t,a;
long int b;
cin>>t;
while(t--)
{
cin>>a>>b;
cout<<lastdigit(a,b)<<"\n";
}
return 0;
}
int lastdigit(int a,long int b)
{ if(b==0){return 1;}
if(a%10==0){return 0;} //for a=0,10,20
if(a%10==1){return 1;} //for a=1,11
if(a%10==5){return 5;} //for a=5,15
if(a%10==6){return 6;} //for a=6,16
int ret,mod=b%4;
if(a%10==2||a%10==8||a%10==4)//for a=2,12,8,18,4,14
{
if(a%10==8){if(mod==1){mod=3;}else if(mod==3){mod=1;}}
if(a%10==4){if(mod==1||mod==3){mod=2;}else if(mod==2){mod=0;}}
if(mod==1){ret= 2;}
else if(mod==2){ret =4;}
else if(mod==3){ret =8;}
else if(mod==0){ret= 6;}
}
else if(a%10==3||a%10==7||a%10==9)//for a=3,13,7,17,9,19
{
if(a%10==7){if(mod==1){mod=3;}else if(mod==3){mod=1;}}
if(a%10==9){if(mod==1||mod==3){mod=2;}else if(mod==2){mod=0;}}
if(mod==1){ret= 3;}
else if(mod==2){ret= 9;}
else if(mod==3){ret= 7;}
else if(mod==0){ret= 1;}
}
return ret;
}
Use macros, define the function inline so that no need of prototype, short variable names eg, You can use r instead of ret. Although try optimizing your logic before all these. This is just a general approach for the problem you are facing.
Use Exponential squaring for finding the power and apply mod 10 for each multiplication in that function.
Its a O(logn) approach so you will be good to go.Here is the implementation for this question:
int pow(long long a, long long b)
{
if(a == 0 && b == 0) return 0;
int ans = 1;
while(b > 0)
{
if(b%2 == 1)
ans *= a;
a *= a;
a %= 10;
ans %= 10;
b /= 2;
if(ans == 0) break;
}
return ans;
}
why this code shows WA it is working for every output i checked
#include<stdio.h>
int main()
{ long long int b;int a,t,c,l;scanf("%d",&t);
while(t--)
{ scanf("%d%lld",&a,&b);c=a%10;
int arr[11][5]={{0},{1},{6,2,4,8},{1,3,9,7},{6,4},{5},{6},{1,7,9,3},{6,8,4,2},{1,9}};
int d[11]={1,1,4,4,2,1,1,4,4,2};
l=arr[c][b%d[c]];
printf("%d\n",l);
}
return 0;
}
this might help you…this is my solution which got accepted…
quite close to what you are trying to implement…
#include<stdio.h>
int main()
{ int t,s2[]={6,2,4,8},s3[]={1,3,9,7},s4[]={6,4},s7[]={1,7,9,3},s8[]={6,8,4,2},s9[]={1,9};
scanf("%d",&t);
while(t–)
{ long long b,a;
scanf("%lld%lld",&a,&b);
int x=b%4,y=b%2;
if(b==0) { printf("1\n"); continue;}
if(a%10==1||a%10==5||a%10==6) printf("%d\n",a%10);
if(a%10==0) printf("0\n");
if(a%10==2) printf("%d\n",s2[x]);
if(a%10==3) printf("%d\n",s3[x]);
if(a%10==4) printf("%d\n",s4[y]);
if(a%10==7) printf("%d\n",s7[x]);
if(a%10==8) printf("%d\n",s8[x]);
if(a%10==9) printf("%d\n",s9[y]); }
You must observe and make a formula it won’t take much memory here is solution
/* CHANDAN KUMAR
CSE / #include <stdio.h>
long long int a,p,q,b;
int t;
int main(void) {
scanf("%d",&t);
while(t–) {
scanf("%lld %lld",&a,&b);
p=a%10;
q=b%4;
if(b==0)
printf(“1\n”);
else if(p==1||p==0||p==5||p==6)
printf("%d\n",p);
else if(q==1)
printf("%d\n",p);
else if(q==2)
printf("%d\n",((pp)%10));
else if(q==3)
printf("%d\n",((ppp)%10));
else if(q==0)
printf("%d\n",((ppp*p)%10));
}
return 0;
}