There have been a few posts here and elsewhere on improving Python performance that I'd search for, but one solution that often works is to use PyPy. See 17765365.

I think that the reason is integer overflow.

Since you uses l, r = 0, 2000000010, the g = (l + r) / 2 instruction can overflow the max integer value 2³¹ - 1.

In C/C++, this would mean Wrong answer. In Python, this only means that the integer will be upgraded internally (without you noticing) to a more expensive integer type, which has arbitrary precision. Of course, the arbitrary precision integer has some overhead, which in your case led to Time limit exceeded.

If you use g = l + (r - l) / 2, you always stay inside the standard integer range, so Python has no need to upgrade to arbitrary precision integer.

For this sort of Binary Search problems i.e. you need to find the maximum value you can get under the constraint you should always use mid = ( low + high + 1 ) / 2.

Why the added 1 ? Look at your implementation and see that there is a scope for infinite loop . If you are stuck you can see the Topcoder tutorial . Hope this helps :)