Valid Perfect Square — Binary Search Without Built-ins [LC 367, Google]

Problem Statement#

Given a positive integer num, return true if num is a perfect square, or false otherwise. You must not use any built-in library function such as sqrt.

Constraints:

• 1 <= num <= 2^31 - 1

Input:  num = 16
Output: true
Explanation: 4 * 4 = 16

Input:  num = 14
Output: false
Explanation: No integer k satisfies k * k = 14.

Why This Problem Matters#

LC 367 is the perfect-square companion to LC 69 (Sqrt(x)). It appears in Google and Apple phone screens as a warm-up binary search problem. The constraint "no built-in sqrt" forces candidates to either binary search or use a mathematical identity — both of which demonstrate algorithmic thinking over library calls.

The binary search approach here uses the standard inclusive template (while lo <= hi) rather than the boundary variant, because you are searching for an exact value rather than a boundary. Recognising which template applies is itself a useful exercise.

The odd-number identity (n^2 = 1 + 3 + 5 + ... + (2n-1)) is a fun mathematical insight but runs in O(sqrt(n)) — mentioning it shows mathematical breadth, but binary search is always the preferred interview answer.

The Core Insight#

Binary search on [1, num]. For each midpoint mid, compute mid * mid and compare to num:

• If mid * mid == num: perfect square, return true.
• If mid * mid < num: the square root is larger, move lo = mid + 1.
• If mid * mid > num: the square root is smaller, move hi = mid - 1.

Overflow: For num near 2^31 - 1, mid can reach ~46,341 and mid * mid can reach ~2.1 * 10^9, which fits in a 32-bit signed integer (max ~2.1 * 10^9). But to be safe in all languages, use 64-bit arithmetic when computing mid * mid.

Tighter bounds: Since sqrt(num) <= num / 2 for all num >= 4, you can set hi = num // 2 with a special case for num <= 3. This halves the initial search range.

Visual Dry Run#

Input: num = 16

Input: num = 14

Solution (Optimal)#

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        if num < 2:
            return True  # 1 is a perfect square
 
        lo, hi = 1, num // 2
 
        while lo <= hi:
            mid = lo + (hi - lo) // 2
            sq = mid * mid  # Python handles large integers natively
 
            if sq == num:
                return True
            elif sq < num:
                lo = mid + 1
            else:
                hi = mid - 1
 
        return False

var isPerfectSquare = function(num) {
    if (num < 2) return true;
 
    let lo = 1;
    let hi = Math.floor(num / 2);
 
    while (lo <= hi) {
        const mid = lo + Math.floor((hi - lo) / 2);
        const sq = mid * mid;  // safe for num <= 2^31-1 since mid <= ~46341
 
        if (sq === num) return true;
        else if (sq < num) lo = mid + 1;
        else hi = mid - 1;
    }
 
    return false;
};

Time: O(log n) — binary search over [1, num/2] Space: O(1) — only pointer variables

Math trick (O(sqrt(n))): Every perfect square is the sum of consecutive odd numbers: 1 = 1, 4 = 1+3, 9 = 1+3+5, 16 = 1+3+5+7. Subtract odd numbers 1, 3, 5, ... until num reaches 0 (perfect square) or goes negative (not).

def isPerfectSquare(num: int) -> bool:
    i = 1
    while num > 0:
        num -= i
        i += 2
    return num == 0

Common Mistakes#

• Using (lo + hi) // 2 — can overflow when lo and hi are both large in 32-bit languages.
• Using int for mid * mid in Java/C++ — cast mid to long before squaring to prevent overflow.
• Returning True when sq == num but inside a while lo < hi loop — the inclusive while lo <= hi template is correct here since you need to check the exact value, not a boundary.
• Setting lo = 0 — 0 * 0 = 0, not num, so starting at 1 is correct. With lo = 0, the first iteration wastes a step.
• Not handling num = 1 — 1 is a perfect square, and with hi = num // 2 = 0, the loop would not run. Add a base case for num < 2.

Interview Tips#

• State the overflow concern immediately when mentioning mid * mid — it shows production-level thinking.
• Mention both the binary search approach and the mathematical identity — offering two approaches shows breadth.
• Use the standard inclusive while lo <= hi template (not the boundary variant) since you are searching for an exact match.
• Compare to LC 69 (Sqrt(x)): LC 69 needs the right-boundary template (finding the largest valid k), while LC 367 uses the exact-match template.

Follow-up Questions#

• LC 69 (Sqrt(x)): Find the integer square root (floor). Requires the right-boundary template, not this exact-match template.
• Is num a perfect cube? Binary search for k where k * k * k == num. Same template, different exponent.
• How would Newton's method work? Start with k = num, iterate k = (k + num / k) / 2 until k * k <= num. Converges quadratically but requires careful termination.
• Can you check all perfect squares up to num in O(1) space? A Bloom filter or Sieve approach works for checking multiple numbers, but for a single number binary search is optimal.

Key Takeaways#

• LC 367 uses the standard inclusive binary search (while lo <= hi, return true on exact match) — not the boundary variant, since you are looking for an exact value.
• Set hi = num // 2 (with a base case for num < 2) to halve the initial search range — sqrt(num) <= num/2 for all num >= 4.
• Always compute mid * mid in 64-bit arithmetic in statically typed languages — for mid ~ 46341, mid^2 ~ 2.1 * 10^9 which is at the edge of 32-bit signed integer range.
• The odd-number identity (subtract 1, 3, 5, ... until 0 or negative) is mathematically elegant but runs in O(sqrt(n)) — mention it but use binary search as the primary answer.
• This problem is structurally simpler than LC 69: LC 69 finds the floor square root (right boundary), LC 367 just checks existence (exact match).
• Google and Apple ask this as a warm-up to verify binary search template fluency before proceeding to harder variants.
• Always distinguish between the three binary search templates: exact match, left boundary, and right boundary — each applies to different problem types.