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))
How is it faster or simpler than just
>>> 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
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.
I see, it is obvious, I should have seen that. BTW, the way you used to test algorithm speed is really nice!
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.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.