💬 Discord
Sign In
NeetCode #264LC-367EasyBinary Search
← Back to All Problems

#264 · #367 · Valid Perfect Square(有效的完全平方数)

📌 Problem Statement & Constraints

Given a positive integer num, return true if it is a perfect square, i.e. it equals k * k for some integer k. You must not use any built-in square-root function. Constraints: 1 <= num <= 2^31 - 1.

💡 Core Algorithmic Approaches

  1. Binary search for the integer square root over [1, num] (or [1, num // 2] for a tighter range when num > 1).
  2. If any midpoint squares exactly to num, return true.
  3. Alternatively, use the property that perfect squares are sums of consecutive odd numbers 1 + 3 + 5 + ..., which gives an O(sqrt(n)) loop.
  4. The binary search is O(log n) and is the expected answer.

💻 Benchmark Python3 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
            if sq < num:
                lo = mid + 1
            else:
                hi = mid - 1
        return False


# Odd-number accumulation: perfect squares are sums of the first k odd numbers
class Solution2:
    def isPerfectSquare(self, num: int) -> bool:
        i = 1
        while num > 0:
            num -= i
            i += 2
        return num == 0

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(log n) for binary search; O(sqrt(n)) for the odd-number accumulation.
💾 Space Complexity
O(1): a few scalars.

⚠️ Interview Pitfalls & Follow-ups

  • Using math.sqrt(num).is_integer(): the problem forbids built-in square-root functions, and floating-point rounding can misjudge values near the 2^31 boundary.
  • Using num 0.5**: same precision concern and also a built-in operator.
  • Setting hi = num // 2: safe only for num > 1; for num = 1 the range would be empty. Using hi = num is simplest and still O(log n).
  • Overflowing mid * mid in fixed-width languages: for num near 2^31 this is fine in 64-bit, but Python is unconditionally safe.