Find Last Digit Of a^b for Large Numbers

general
, ,
1

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

Link of Question

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];
}
2

Refer this → Modulo power for large numbers represented as strings - GeeksforGeeks

3

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.