TLE in fast fibonacci

#1

I solved this question using matrix exponentiation still I am getting error in 3 test cases. Why is this happening? Please help.
My code: https://ide.codingblocks.com/s/259542

#2

@akshat_jain
Hey Akshat! Your logic is correct but there are few mistakes

  1. your code don’t work for n=1, so change condition in line 39 to if(n<=1)
  2. you are calculating the same power(a,n/2,k) two line in line no 42 and 45. Which has increase the time complexity of your. Just store power(a,n/2,k) somewhere else and then use it. Changing power() function like this would work.

vvi power(vvi a,int n,int k){
if(n<=1)
return a;
vvi as = power(a,n/2,k);
if(n&1){
vvi b=multiply(as,as,k);
return multiply(a,b,k);
}
return multiply(as,as,k);
}

#3

@akshat_jain
Please mark this doubt as resolved. thanks :grinning:

#4

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.