# Python runtime limited

• ``````def pow(self, x, n):
if n == 0:
return 1
if x == 0 and n < 0:
return
result = 1
if n > 0:
while n > 0:
pre_result = result
result *= x
if pre_result == result or pre_result == -result:
if result >= 0:
return result
if n % 2 == 0:
return -result
else:
return result
n -= 1
return result
else:
while n < 0:
pre_result = result
result /= x
if pre_result == result or pre_result == -result:
if result >= 0:
return result
if n % 2 == 0:
return -result
else:
return result
n += 1
return result
``````

my code is like the above.
it has time limited error with the test case:
-1.00000, -2147483648
but I think for my solution, it should be very quick and I tested in my computer, it will take less than 1 ms,
what's wrong with my solution?
Thank you very much!

• x^n = xx...x
so you do multiplication n times,of course it may lead to time limited error,you should try some other solutions.
x^n =x^n/2
x^n/2
and you can see you just need to calculate the result of x^n/2

• Your solution is O(n), and it would excess the time limit while n is very big.
A hint here: to count 4^64, you just need to count (((((4^2)^2)^2)^2)^2)^2), so you could reduce the number of iteration from 64 to 6 (O(logn)). This is the simplest case, as for the condition where n is not the power of 2, such as 4^63, you could recursively divide that 63 into several pieces:

4^63 = (4^32) * (4^16) * (4^8) * (4^4) * (4^2) * (4^1) = (((((4^2)^2)^2)^2)^2) * ((((4^2)^2)^2)^2) * (((4^2)^2)^2) * ((4^2)^2) * (4^2) * (4^1)

In this case (worst one), we need 16 iterations (5+4+3+2+1+1), still much better than O(n)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.