4 TCs givig TLE in Fibonacci meets gcd problem

#1

my sol : https://ide.codingblocks.com/s/254744

2 TCs got ac while remaining 4 r giving TLE !!

i don’t why it is so as my code is optimal from every point and it makes no sense of TLE !!!

i think there is some problem with the TCs of problems in segment tree challenge section; please look into it as 2-3 more problems r giving TLE on some of TCs even though my sol is optimal

pls help me out!

#2

@saarthakseth,
Recursion is slow, specially when time constraints are tight, we should try to avoid it as much as possible.
Use __gcd(), rather than your own recursive one. Also, do matrix exponentiation iteratively rather than recursively.

#3

same result even after using __gcd() instead of my own gcd function

#4

i don’t think that __gcd() would have had any effect as my gcd func also took O(logn) time only

#5

btw i think i’ve done matrix exp iteratively only ; i’ve just calc power recursively nothing else !

#6

can u pls tell how to optimize my matrix exp function ??

#7

@saarthakseth,
Write iterative function for power as well as gcd(rather use __gcd()).

#8

but iterative func of power will take O(n) time nd my recursive one is taking O(logn) only

#9

how can i write power func iterarively in O(log n) ??

#10

@saarthakseth,
Here.

#11

this one i know ! but this is for nos and here we have to find pow of a matrix

#12

ok lemme try implementing it for matrix nd submitting

#13

but the time complexities r same for both , then how will it effect in avoiding TLE ??

#14

my updated code : https://ide.codingblocks.com/s/256934

#15

still giving TLE on the same TCs ; i think maybe the TCs r wrong or may be exceeding the constraints themselves

#16

@saarthakseth,
Maybe you are correct, I will try that the required updates are made.

#17

@saarthakseth,
You can try submitting now, problem has been updated.

#18

1 TC still giving TLE !

#19

and can u pls get the problems array queries-1 and matrix queries-1 as they r too giving TLE even though my sol is optimal for them

#20
  • get those problem’s TCs checked