# Find Last Digit Of a^b for Large Numbers

// I am solving this question but I am getting TLE
// Can anyone suggest me any other logic??

``````void multiply(int x,vector<int>&vec){
int carry = 0;

for(int i=0;i<vec.size();i++){
int temp;
temp = vec[i]*x + carry;

vec[i] = temp%10;

carry = temp/10;
}

while(carry){
vec.push_back(carry%10);
carry = carry/10;
}
}

int getLastDigit(string a, string b){
int x = 0;
for(int i=0;i<a.size();i++){
x = x*10 + (a[i]-'0');
}

int y = 0;
for(int i=0;i<b.size();i++){
y = y*10 + (b[i]-'0');
}

vector<int>vec;
vec.push_back(1);

for(int i=0;i<y;i++){
multiply(x,vec);
}

return vec[0];
}``````

You can do it in this way.

`````` int getLastDigit(string a, string b) {
vector<int> t(4,0);

int n1,n2,n3;
n1 = a[a.size()-1]-'0';
n2 = b[b.size()-1]-'0';
n3 = 0;
if(b.size() > 1)
n3 = b[b.size()-2]-'0';
for(int i = 0 ; i < 4 ; i++){
t[i] = pow(n1,i+1);
t[i] %= 10;
}

int value = n3*10+n2;
if(value == 0)
return 1;
value = value%4;
return t[(value-1+4)%4];
}
``````

as you know last digit a^b is simply (a%10)^b

eg : 345367^324 is equivalent to 7^324

and you can try it on pen and paper that every thing repeats in steps of 4.so just maintain these 4 powers and you are done.