The last digit

**

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 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;
}
6 Likes

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",((p
p)%10));
else if(q==3)
printf("%d\n",((ppp)%10));
else if(q==0)
printf("%d\n",((ppp*p)%10));
}
return 0;
}

/* 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",((p*p)%10));
else if(q==3)
    printf("%d\n",((p*p*p)%10));
else if(q==0)
    printf("%d\n",((p*p*p*p)%10));
}
return 0;

}

1 Like

you should chech test case of 10^0 at that case your code get result of 0 but it should be 1.@prkstyle…

1 Like

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.

1 Like

@abbas thanks for the answer.I think that’s the best optimization.

You could also substitute z=a%10; to shorten more.

import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenizer;class LASTDIG_The_last_digit_SPOJ{static long mod=2147483000;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){long res=1;while(b!=0) {if((b&1)==1){res=(resa)%mod;–b;}a=(aa)%mod;b/=2;}return res;}}

write the code in a compact format and use modular exponentiation by taking mod value =2147483000.it will be accepted

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.

Can you please give an explanation with the code
Actually i am unable to get through this code

   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