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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Valid Perfect Square

Number: 367

Difficulty: Easy

Paid? No

Companies: Google, Microsoft, LinkedIn, Meta, Apple, Adobe, Bloomberg

Problem Description

Given a positive integer num, determine if num is a perfect square—i.e., whether there exists an integer whose square equals num—without using any built-in library function like sqrt.

Key Insights

  • Recognize that if num is a perfect square, it will have an exact integer square root.
  • Use binary search between 1 and num/2 (when num >= 4) to efficiently determine if there is an integer mid such that mid * mid == num.
  • The binary search stops when the search space is exhausted, meaning num is not a perfect square if no integer mid found.

Space and Time Complexity

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

Solution

We solve the problem using binary search. By checking mid * mid at each step, we narrow down the interval where the square root could lie, eventually determining if an exact integer square root exists. The trick is setting the correct search boundaries: numbers less than 4 can be handled directly, and for larger numbers, the square root can never be more than num/2. This avoids using built-in functions and deals gracefully with large inputs.

Code Solutions

# Function to determine if a number is a perfect square using binary search.
def isPerfectSquare(num):
    # If num is less than 2, it is a perfect square (e.g., 1).
    if num < 2:
        return True
    # Set initial boundaries for binary search.
    left, right = 2, num // 2
    while left <= right:
        # Calculate mid point.
        mid = left + (right - left) // 2
        guessed_square = mid * mid
        # Check if the mid value squares to num.
        if guessed_square == num:
            return True
        # If guessed square is too high, discard right half.
        elif guessed_square > num:
            right = mid - 1
        # Otherwise, discard left half.
        else:
            left = mid + 1
    return False

# Example usage:
print(isPerfectSquare(16))  # True
print(isPerfectSquare(14))  # False
← Back to All Questions