Recently I did a Gym competition as a virtual contest. I was not able to do Problem D. Largest Group. After completion of the contest, I tried to implement the editorial solution of this given problem. The editorialist is saying that a solution of time complexity O((2^P)*P) will pass. But my solution is giving TLE in test case 2.
Why is my code giving TLE? Is there any other good solution for this problem?
This is my code which I implemented as said in editoiral.
Change pow(2,p) to (1<<p) and it will get AC. pow(2, p) is too slow and it executes on each iteration in your code.
Why not just assign (1<<p) to a variable? That will eliminate even the bit shifting.
well, 2^p binary shifts will not change the complexity as it is just simple operation, so assigning it to variable will not help at all. function pow got some exponentiation with doubles, so it is very heavy compared to simple binary shifting.