Python submission Time Limit Exceeded


  • 0
    Y

    My solution is:

    class Solution:
    # @param x, a float
    # @param n, a integer
    # @return a float
    def pow(self, x, n):
        p, newp, y = 0, 1, abs(x)
        if n < 0 :
            y, n = 1.0/y, -n
        while p != newp:
            p = newp
            if n == 0:
                break
            else:
                newp, n = p * y, n - 1
        return -p if x < 0 and n % 2 else p
    

    It gets Time Limit Exceed at -1.00000, -2147483648.
    But, I can get the result on my own desktop.
    Can anyone explain what was wrong with my code?

    Actually, it needs only one iteration to get the answer for this input ...


  • 0
    Z
    This post is deleted!

  • 0
    Z

    But you compared a float with an int. Could it be a reason?


  • 0
    Y

    Thank you for your suggestion. I changed the last line to

    {return -p if x < 0.0 and n % 2 else p}

    Still Time Limit Exceed at the same test.

    Since I am using python 2.7.6 on my own computer and OJ uses 2.7.5, I guess it is related to some changes during the upgrade.


  • 0
    K

    Your solution is O(n). This can be implemented in O(log(n))


  • 0
    Y

    Yes, the best solution should be O(log(n)).
    But for this particular test case, my algorithm only need 1 iteration ...
    My laptop get the answer in a blink.
    Maybe it is because the rounding error of float.


Log in to reply
 

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