Shortest Python - Guaranteed


  • 36

    Surprisingly, I can just use Python's existing pow like this:

    class Solution:
        myPow = pow
    

    That's even shorter than the other more obvious "cheat":

    class Solution:
        def myPow(self, x, n):
            return x ** n
    

    And to calm down the haters, here's me "doing it myself":

    Recursive:

    class Solution:
        def myPow(self, x, n):
            if not n:
                return 1
            if n < 0:
                return 1 / self.myPow(x, -n)
            if n % 2:
                return x * self.myPow(x, n-1)
            return self.myPow(x*x, n/2)
    

    Iterative:

    class Solution:
        def myPow(self, x, n):
            if n < 0:
                x = 1 / x
                n = -n
            pow = 1
            while n:
                if n & 1:
                    pow *= x
                x *= x
                n >>= 1
            return pow

  • 0

    Thank you for sharing although I am kinda confused why the iterative one works. Can you explain it a little bit more?


  • 0
    A

  • 0

    clickbait title!
    but the iterative solution is very cool!!!


  • 0

    @mingrui3 Isn't clickbait usually misleading, though? And I think my title is correct :-)


  • 0

    @StefanPochmann Cause the players gonna play, play, play, play, play. And the haters gonna hate, hate, hate, hate, hate.


  • 0

    @StefanPochmann
    When I implemented basically the exactly same recursive solution as yours, I met a problem. Here is the "wrong" version.

    class Solution(object):
        def myPow(self, x, n):
            """
            :type x: float
            :type n: int
            :rtype: float
            """
            return 1 if not n else 1.0 / self.myPow(x, -n) if n < 0 \
                   else x * self.myPow(x**2, n>>1) if n & 1 else self.myPow(x**2, n>>1)
    

    It shows "Line 9: OverflowError: (34, 'Numerical result out of range')". And if I changed x**2 into x*x, it works. Do you know if there is any "hidden" difference between x**2 and x*x, Stefan?


  • 1

    @realisking An example of the difference:

    >>> x = 1e200
    
    >>> x * x
    inf
    
    >>> x ** 2
    Traceback (most recent call last):
      File "<pyshell#12>", line 1, in <module>
        x ** 2
    OverflowError: (34, 'Result too large')
    

    Multiplications are defined in the IEEE 754 standard. Wikipedia says:

    Overflow (a result is too large to be represented correctly) (returns ┬▒infinity by default

    So that's why x * x simply results in inf in my above test.

    Powers I think aren't covered in the standard, so Python can choose what to do in case of overflow, and chooses to raise an exception.


  • 0

    @StefanPochmann
    Thanks a lot!


  • 0
    R

    JS version of recursive:

    var myPow = function(x, n) {
            if(n == 0)
                return 1
            if (n < 0) {
                return 1 / myPow(x, -n)
            }
            if(n % 2) {
                return x * myPow(x, n-1)
            }
            return myPow(x*x, n/2)
    
    };
    

    Golang version:

    func myPow(x float64, n int) float64 {
            if n == 0 {
                return 1
            }
            if n < 0 {
                return 1 / myPow(x, -n)
            }
            if n % 2 == 1 {
                return x * myPow(x, n-1)
            }
            return myPow(x*x, n/2)
    }
    

Log in to reply
 

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