Hi,
I’m attemting to solve this problem SPOJ LASTDIG2
So far I have used modular exponentiation (recursive procedure), but I’m getting TLE.
Here’s my solution:
#include <bits/stdc++.h>
using namespace std;
int modExpo(int x, int n){
if(n==0){
return 1;
}else if(n == 1){
return x%10;
}else if(n&1){
return (modExpo(x, 1) * modExpo(x, n-1)) % 10;
}else{
int temp = modExpo(x, (n/2));
return (temp * temp) % 10;
}
}
int main(){
int t;
long long b;
string s;
scanf("%d",&t);
while(t--){
cin>>s;
scanf("%lld", &b);
int a = s[s.length()-1] - '0';
printf("%d\n", modExpo(a,b));
}
return 0;
}
Can somebody tell my why I’m getting TLE when modular exponentiation is the right way to solve this?
I thought about memoizing the subproblems but I’m not sure about how many different subproblems (<x, n> pairs) can be there. So could not be sure about which data structure to use to store the subproblems.
Thanks!