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;
- 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”.
convert_back(binary) - This takes binary number in form of string and returns its corresponding base 10 integer.
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.
Thank you for the help.