Python runtime limited


  • -1
    J
    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!


  • 0
    L

    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


  • 1
    P

    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)


Log in to reply
 

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