Domain 1EasyCORE

Valid Perfect Square

The problem asks us to determine whether a given positive integer `num` is a perfect square. A perfect square is an integer that is the square of another integer. For example, 16 is a perfect square because it can be expressed as 4 * 4.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Math#Binary Search

367. Valid Perfect Square

Model: qwen2.5-coder:14b
Topics: Math,Binary Search
FAANG asked: 1
Acceptance rate: 42.2%


Problem Breakdown

The problem asks us to determine whether a given positive integer num is a perfect square. A perfect square is an integer that is the square of another integer. For example, 16 is a perfect square because it can be expressed as 4 * 4.

Inputs:

  • A single positive integer num (1 <= num <= 2^31 - 1).

Outputs:

  • A boolean value: True if num is a perfect square, otherwise False.

Implicit Constraints or Tricky Edge Cases:

  • The input range is quite large (up to 2^31 - 1), so the solution must be efficient in terms of time and space.
  • We cannot use any built-in library functions like sqrt.
  • Consider edge cases such as the smallest number, 1, which is a perfect square.

Intuition

A brute-force approach would involve iterating from 1 to num and checking if the square of any number equals num. However, this approach has a time complexity of O(n), which is inefficient for large values of num.

The key insight is that we can use binary search to efficiently determine whether num is a perfect square. Binary search reduces the time complexity to O(log n) by repeatedly dividing the search interval in half.

Approach

  1. Initialize Pointers: Set two pointers, left and right, where left starts at 1 and right starts at num // 2. We start right at num // 2 because any perfect square greater than 1 will have its square root less than or equal to num // 2.
  2. Binary Search Loop:
    • Calculate the midpoint mid between left and right.
    • Compute mid * mid.
    • If mid * mid equals num, then num is a perfect square, return True.
    • If mid * mid is less than num, move the left pointer to mid + 1.
    • If mid * mid is greater than num, move the right pointer to mid - 1.
  3. Termination: The loop terminates when left exceeds right. If no perfect square is found, return False.

Complexity Analysis

  • Time Complexity: O(log n) because we are using binary search.
  • Space Complexity: O(1) as we are only using a constant amount of extra space for the pointers and variables.

Solution

def isPerfectSquare(num: int) -> bool:
    if num < 2:
        return True
    
    left, right = 1, num // 2
    
    while left <= right:
        mid = (left + right) // 2
        square = mid * mid
        
        if square == num:
            return True
        elif square < num:
            left = mid + 1
        else:
            right = mid - 1
    
    return False

Edge Cases Handled

  • Edge Case: Smallest Input (num = 1): The function correctly identifies that 1 is a perfect square.
  • Edge Case: Largest Input (num = 2^31 - 1): The function efficiently handles the largest possible input within the given constraints.
  • Edge Case: Non-perfect Square: The function correctly returns False for numbers like 14, which are not perfect squares.