Facing TLE despite algorithm being efficient

The question: https://www.codechef.com/LTIME89B/problems/SSO
My solution : https://www.codechef.com/viewsolution/39268467
Editorial: [SSO - Editorial]

Since there is a nested loop present in the driver code the time complexity becomes O(n*length) which is equivalent to O(NlogN). This should work within the time limit of 1 sec because N<=10^5.

Explanation of code: I have created three functions apart from the main function;

  1. convert(num, length) - This takes two parameters “num” and “length” and returns a string that is the binary representation of “num” having a length “length”. Because of the code it is guaranteed that “length”>= actual length of the binary representation of “num”. Ie. 0’s are appended to the front of the binary representation of “num” to achieve desired “length”.
  1. convert_back(binary) - This takes binary number in form of string and returns its corresponding base 10 integer.

  2. len(num) - Returns length of binary representation of “num”.


I have considered that all functions are taking O(1) time as the time taken is more or less same for every parameter.

(SSO - Editorial)

Thank you for the help.