I am unable to understand the time complexity of subsfreq problem from august long challenge

here’s my code (for sub-task 2) -https://www.codechef.com/viewsolution/36867146 ,which i think should work fine as i am calculating the first value(2^(n-1)) using binary exponentiation,and after that i am dividing every value by 2.

Can i know why it exceeds time limit.

Edit -I am sorry i provided a different code link now i have corrected it.

There is no modulo so the number gets really big and I think python cant handle multiplications for really big numbers(2^100000) so it just takes forever to multiply.

Try using this function here: https://www.geeksforgeeks.org/modular-exponentiation-power-in-modular-arithmetic/

1 Like