Valid Perfect Square

How it works

We can construct the square root bit by bit, from the most significant bit to the least significant. For a 32-bit integer, the square root fits in at most 16 bits. We try setting each bit position and check if the resulting number squared is still within bounds. If setting a bit makes the square too large, we clear that bit; otherwise, we keep it. This builds the largest integer whose square does not exceed the input.

Steps

1. Initialize r = 0 and mask = 1 << 15 (starting from the highest possible bit).
2. While mask > 0:
   • Set the current bit: r |= mask.
   • If r > num / r (meaning r^2 would exceed num), clear the bit: r ^= mask.
   • Shift the mask right: mask >>= 1.
3. After processing all bits, check if r * r == num.
4. Return true if equal, false otherwise.

Complexity

• Time complexity: O(1) since we iterate at most 15 times.
• Space complexity: O(1)

Things to watch for

Integer Overflow When Squaring

When computing m * m in binary search or brute force approaches, the result can overflow if using 32-bit integers. For example, if m = 46341, then m * m = 2147488281 which exceeds the maximum 32-bit signed integer. Always use long or long long for the squared value, or use division (m > num / m) to avoid overflow.

Floating-Point Precision Issues

When using the built-in sqrt() function, floating-point precision can cause incorrect results. For example, sqrt(2147395600) might return 46339.999989... which truncates to 46339 instead of 46340. Always verify by squaring the integer result and comparing with the original number, rather than relying solely on the floating-point square root.

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        r, mask = 0, 1 << 15

        while mask > 0:
            r |= mask
            if r > (num // r):
                r ^= mask
            mask >>= 1

        return r * r == num

class Solution {
public:
    bool isPerfectSquare(int num) {
        int r = 0, mask = 1 << 15;

        while (mask > 0) {
            r |= mask;
            if (r > (num / r)) {
                r ^= mask;
            }
            mask >>= 1;
        }

        return r * r == num;
    }
};