We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Valid Perfect Square

Difficulty: Easy

Problem Description

Given a positive integer num, return true if num is a perfect square or false otherwise. A perfect square is an integer that is the square of an integer, meaning it is the product of some integer with itself. You must not use any built-in library function, such as sqrt.

Key Insights

  • A perfect square can be determined by finding an integer whose square equals the given number.
  • We can use a binary search approach to efficiently find the integer square root of the number.
  • The search space for the integer square root can be limited between 1 and num.

Space and Time Complexity

Time Complexity: O(log(num))
Space Complexity: O(1)

Solution

To determine if a number is a perfect square, we can perform a binary search. We will set our search range between 1 and num. In each iteration, we calculate the middle point and check if its square equals the given number. If it is less, we move our search to the right half; if it is more, we move to the left half. If we find a perfect square, we return true; otherwise, we return false.

Code Solutions

def isPerfectSquare(num):
    if num < 1:
        return False
    
    left, right = 1, num
    while left <= right:
        mid = left + (right - left) // 2
        square = mid * mid
        
        if square == num:
            return True
        elif square < num:
            left = mid + 1
        else:
            right = mid - 1
            
    return False
← Back to All Questions