Valid Perfect Square

Intuition

If the number has an integer square root, that root lies somewhere between 1 and the number itself. Because squaring is monotonic over positive integers, we can binary search for the root: compare a candidate squared against the target and shrink the search window based on whether it overshot or fell short. Widening the intermediate value to a 64-bit type avoids overflow when squaring near the upper limit.

Algorithm walkthrough

1. 1Set lo to 1 and hi to num as the inclusive bounds for the root.
2. 2While lo does not exceed hi, take the midpoint and square it.
3. 3If the square equals num, the number is a perfect square, so return true.
4. 4If the square is too small, raise lo above mid; if too large, lower hi below mid.
5. 5If the window empties without a match, return false.

Implementation

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

Intuition

Newton's method for square roots repeatedly replaces a guess x with the average of x and num/x, which converges very quickly toward the true root. Doing this in integer arithmetic drives x down to the floor of the square root; once it settles, squaring that value and comparing to the original number confirms whether the number was a perfect square.

Algorithm walkthrough

1. 1Start with a guess x equal to num.
2. 2While x squared still exceeds num, update x to the integer average of x and num divided by x.
3. 3The loop lowers x until it reaches the floor of the square root.
4. 4Return true only if that final x squared exactly matches num.

Implementation

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        x = num
        while x * x > num:
            x = (x + num // x) // 2
        return x * x == num