Why am I getting TLE in normal approach and not in Precomputation?

XOR Equality - May Long Challenge 2021
Precomputation is used on the left side and normal approach is followed on the right side.

The answer is in the question itself.

2 Likes

Can you help me out with this? Iā€™m unable to get what you are trying to say.

Precomputation reduces the time complexity to O(MX), where MX is the size of input.
While if you do it for each test case separately than the time complexity will be O(T x MX).

So if the input size if 10^5 and test cases are also upto 10^5, than obviously it will not execute in 1sec and you are getting TLE.

Precomputation reduces the number of operations to maximum size of input only.