Question->SPOJ.com - Problem 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 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;
}
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.
Can u explain the logic here more specifically?
I am new to the platform and reading various articles to help me understand unknown concepts and tips & tricks.
static long mod=2147483000; // this is the maximum value of b i.e. power
public static void main(String[] args) throws java.lang.Exception
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t=Integer.parseInt(br.readLine());
while(t–>0){
StringTokenizer st=new StringTokenizer(br.readLine());
long a=Long.parseLong(st.nextToken()),b=Long.parseLong(st.nextToken());
System.out.println(Modular_Expo(a,b)%10);
}
}
static long Modular_Expo(long a, long b) { // O(log(b))
long res=1;
while(b!=0) {
if((b&1)==1) {res=(res*a)%mod;--b;}
a=(a*a)%mod;b/=2;
}
return res;
}
here I have used modular exponentiation_method. In modular exponentiation if the power is even then number a should be multiplied by itself and power b will be reduced by b/2 and if b is odd in result we will be adding a in res by multiplying a with the previous value of res and at that time power b will be reduced by 1.and I have taken the maximum value of mod to be largest value of b to avoid overflow . after that apply that function on main function and original result will be
res%10.
it will give the last digit.
as source limit is 700 B write the code in a compact way or in 1 line