The constraints are N ≤ 10^9 and the above is an O(N^2) solution. The problem’s time limit is 5 seconds (multiplier for python), and the above solution takes 0.71 seconds.
Theoretically, this is supposed to take 9999999990 seconds (Assuming 10^8 operations ≈1 second) for the worst case for each testcase. There are 1000 testcases at max.
It would take at least 10 times more as the language is python.
Maybe i’m getting the logic wrong but isn’t it just the first one in binary or if it is a power of 2 then just the -1, so it should be O(Tlogn) which should work in 0 seconds
I put 2^{60} =1.18 \times 10^{18} in 10^5 testcases and then i got 0.01 seconds on my code for the sum. The constraints were very small. 2^{60} takes the most time to compute.
If it the question was intended to be easy, the constraints should have been small so that those who participate won’t be misled and try solve it for the given constraints.
The testcases are quite bad …
The problem states that if there is no number a and b can be found , print -1
But the program of yours does not have that condition …
the answer for a is always 1, 2 ,4 , … any power of 2 . .
So the complexity is O (log N) in worst case (If N is power of 2 ) and O(1) if N is odd
If you amortize the complexity, both of our solutions have the same O(log_2 n)
Also, please note that I solved the problem during the contest. After the contest ends, one can improve their solution by spending more time on it. During the contest, you’d just want to solve a problem and move on.
