367. Valid Perfect Square – Leetcode Solutions

Example 1:

Input: num = 16
Output: true
Explanation: We return true because 4 * 4 = 16 and 4 is an integer.

Example 2:

Input: num = 14
Output: false
Explanation: We return false because 3.742 * 3.742 = 14 and 3.742 is not an integer.
 

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        # Edge case: if num is 1, it's a perfect square (1 * 1 = 1)
        if num == 1:
            return True
        
        # Initialize the binary search bounds
        left, right = 1, num
        
        # Perform binary search
        while left <= right:
            # Calculate the middle value
            mid = left + (right - left) // 2
            squared = mid * mid
            
            # Check if the mid value squared equals num
            if squared == num:
                return True
            # If mid^2 is less than num, move to the right half
            elif squared < num:
                left = mid + 1
            # If mid^2 is greater than num, move to the left half
            else:
                right = mid - 1
        
        # If no perfect square is found, return False
        return False

class Solution {
public:
    // Function to check if the given number is a perfect square
    bool isPerfectSquare(int num) {
        // Handle the special case where the number is 1
        if (num == 1) return true;
        
        // Initialize the binary search bounds
        long long left = 1, right = num;

        // Binary search to find if there's a number whose square equals num
        while (left <= right) {
            // Calculate the middle value
            long long mid = left + (right - left) / 2;
            
            // Compute the square of mid
            long long square = mid * mid;

            // If we find a perfect square, return true
            if (square == num) {
                return true;
            } 
            // If the square is too large, search in the lower half
            else if (square > num) {
                right = mid - 1;
            } 
            // If the square is too small, search in the upper half
            else {
                left = mid + 1;
            }
        }

        // If no perfect square is found, return false
        return false;
    }
};

var isPerfectSquare = function(num) {
    // Edge case for 1, since 1 * 1 is 1 (itself a perfect square).
    if (num === 1) return true;
    
    // Start checking from 1, initialize the left and right boundaries.
    let left = 1;
    let right = num;
    
    // Use binary search to find the square root or to determine it doesn't exist.
    while (left <= right) {
        // Calculate the middle number.
        let mid = Math.floor((left + right) / 2);
        
        // Check if mid * mid equals the number.
        let squared = mid * mid;
        
        if (squared === num) {
            // If mid * mid equals num, then it's a perfect square.
            return true;
        } else if (squared < num) {
            // If mid * mid is less than num, we need to search in the higher half.
            left = mid + 1;
        } else {
            // If mid * mid is greater than num, we need to search in the lower half.
            right = mid - 1;
        }
    }
    
    // If no integer square root was found, return false.
    return false;
};

class Solution {
    public boolean isPerfectSquare(int num) {
        // Edge case: If num is less than 1, return false because it cannot be a perfect square
        if (num < 1) {
            return false;
        }

        // Initialize low and high for binary search
        long low = 1;
        long high = num;

        // Binary search to find if there exists an integer 'mid' such that mid * mid = num
        while (low <= high) {
            long mid = low + (high - low) / 2; // To prevent overflow

            // Calculate the square of mid
            long square = mid * mid;

            // If mid * mid equals num, then num is a perfect square
            if (square == num) {
                return true;
            } 
            // If square is greater than num, reduce the search space to the left (lower numbers)
            else if (square > num) {
                high = mid - 1;
            } 
            // If square is less than num, increase the search space to the right (higher numbers)
            else {
                low = mid + 1;
            }
        }

        // If no such mid is found, num is not a perfect square
        return false;
    }
}