Skip to main content
Performance tag added since OP is concerned about runtime
Source Link
Stephen Rauch
  • 4.2k
  • 12
  • 23
  • 36

I am working on Valid Perfect Square - LeetCode
  and wrote a standard leftmost bisect search to solve the problem:

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        #base case 1
        if num == 1: return True 
        lo = 1
        hi = num
        #recur case 
        while lo < hi:
            mid = (lo + hi) // 2
            if num > mid ** 2:
                lo = mid + 1
            else:
                hi = mid 
        return True if lo ** 2 == num else False

HoeverHowever, the score is annoying:

Runtime: 48 ms, faster than 24.22% of Python3 online submissions for Valid Perfect Square. Memory Usage: 13.2 MB, less than 5.17% of Python3 online submissions for Valid Perfect Square.

I am not able to improve a standard template a little bit.

Could you please provide any advice?

I am working on Valid Perfect Square - LeetCode
  and wrote a standard leftmost bisect search to solve the problem

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        #base case 1
        if num == 1: return True 
        lo = 1
        hi = num
        #recur case 
        while lo < hi:
            mid = (lo + hi) // 2
            if num > mid ** 2:
                lo = mid + 1
            else:
                hi = mid 
        return True if lo ** 2 == num else False

Hoever, the score is annoying

Runtime: 48 ms, faster than 24.22% of Python3 online submissions for Valid Perfect Square. Memory Usage: 13.2 MB, less than 5.17% of Python3 online submissions for Valid Perfect Square.

I am not able to improve a standard template a little bit.

Could you please provide any advice?

I am working on Valid Perfect Square - LeetCode and wrote a standard leftmost bisect search to solve the problem:

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        #base case 1
        if num == 1: return True 
        lo = 1
        hi = num
        #recur case 
        while lo < hi:
            mid = (lo + hi) // 2
            if num > mid ** 2:
                lo = mid + 1
            else:
                hi = mid 
        return True if lo ** 2 == num else False

However, the score is annoying:

Runtime: 48 ms, faster than 24.22% of Python3 online submissions for Valid Perfect Square. Memory Usage: 13.2 MB, less than 5.17% of Python3 online submissions for Valid Perfect Square.

I am not able to improve a standard template a little bit.

Could you please provide any advice?

Performance tag added since OP is concerned about runtime
Link
Source Link
Wizard
  • 449
  • 2
  • 7

Leftmost bisect search to find valid perfect square

I am working on Valid Perfect Square - LeetCode
and wrote a standard leftmost bisect search to solve the problem

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        #base case 1
        if num == 1: return True 
        lo = 1
        hi = num
        #recur case 
        while lo < hi:
            mid = (lo + hi) // 2
            if num > mid ** 2:
                lo = mid + 1
            else:
                hi = mid 
        return True if lo ** 2 == num else False

Hoever, the score is annoying

Runtime: 48 ms, faster than 24.22% of Python3 online submissions for Valid Perfect Square. Memory Usage: 13.2 MB, less than 5.17% of Python3 online submissions for Valid Perfect Square.

I am not able to improve a standard template a little bit.

Could you please provide any advice?