Python trivial Solution 52ms 96%


  • -1
    D

    I tried solutions using binary search and Newton Method, but the fastest and simplest solution I got is this.....So I would not use it in a job interview, but definitely in my daily work.

    from math import sqrt
    class Solution(object):
        def mySqrt(self, x):
            """
            :type x: int
            :rtype: int
            """
            if x < 2:
                return x
            else:
                return int(sqrt(x))

  • 1

    How is it faster or simpler than just return int(sqrt(x))?

    >>> from math import sqrt
    >>> from timeit import timeit
    >>> r, n = range(1000000), 10
    
    >>> class Solution(object):
            def mySqrt(self, x):
                if x < 2:
                    return x
                else:
                    return int(sqrt(x))
    
    >>> timeit(lambda: map(Solution().mySqrt, r), number=n)
    8.927773504978006
    
    >>> class Solution(object):
            def mySqrt(self, x):
                return int(sqrt(x))
    
    >>> timeit(lambda: map(Solution().mySqrt, r), number=n)
    8.070402839847418
    

  • 0
    D

    Good point, it is not faster.But I used some negative test cases to see what the OJ return. To my surprise, OJ gives the same value, so I added that if statement.


  • 0

    Well, that's just because of how the OJ's solution happens to be coded. Invalid input leading to meaningless output. It's not the same for all languages, btw, in C++ for example I just got expected output -2147483648 for input -5, and in Javascript it expects 0 for that.


  • 0
    D

    I see, it is obvious, I should have seen that. BTW, the way you used to test algorithm speed is really nice!


  • 0

    Ha, actually I just realized I did something pointless. I did sum(map(...)), which I guess is a habit from Python 3. Here we have Python 2, so map(...) suffices. Changed that now, times got slightly faster.


  • 0

    And extracted range(1000000) now to take it out of the timing (also makes it a bit clearer that the two tests are the same).


  • 0
    D

    Yep, the comparison method is improved! I have saved it as a template :)


Log in to reply
 

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