Valid Perfect Square

EASY

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. In other words, it is the product of some integer with itself.

You must not use any built-in library function, such as sqrt.

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.

Constraints:

1 <= num <= 2³¹ - 1

Approaches

Checkout 3 different approaches to solve Valid Perfect Square. Click on different approaches to view the approach and algorithm in detail.

Brute Force: Linear Search

This approach iterates through numbers from 1 up to num and checks if the square of any number i equals num. To optimize, we only need to iterate as long as i * i <= num.

Algorithm

Initialize a long variable i to 1.
Loop as long as the square of i is less than or equal to num.
Inside the loop, check if i * i is equal to num.
If it is, return true.
If the loop finishes without finding such an i, it means num is not a perfect square, so return false.

The most straightforward method is to check every integer i starting from 1 to see if its square is equal to the given number num.

We can start a loop with a counter i (as a long to prevent overflow when squaring) from 1.

In each iteration, we calculate the square of i.

If i * i equals num, we have found an integer whose square is num, so num is a perfect square, and we can return true.
If i * i exceeds num, it means that the square of i and any subsequent integer will also be greater than num. Therefore, num cannot be a perfect square, and we can stop the search and return false.

This method is simple but can be slow for very large values of num.

class Solution {
    public boolean isPerfectSquare(int num) {
        if (num < 1) return false;
        if (num == 1) return true;
        
        for (long i = 1; i * i <= num; i++) {
            if (i * i == num) {
                return true;
            }
        }
        return false;
    }
}

Complexity Analysis

Time Complexity: O(sqrt(n)), where n is the input number `num`. In the worst case, we iterate from 1 up to `sqrt(num)`.Space Complexity: O(1), as we only use a constant amount of extra space for the loop variable.

Pros and Cons

Pros:

Simple to understand and implement.
Requires minimal memory.

Cons:

Inefficient for large input numbers.
May result in a 'Time Limit Exceeded' error on platforms with strict time limits.

Code Solutions

Checking out 3 solutions in different languages for Valid Perfect Square. Click on different languages to view the code.

class Solution { public boolean isPerfectSquare ( int num ) { long left = 1 , right = num ; while ( left < right ) { long mid = ( left + right ) >>> 1 ; if ( mid * mid >= num ) { right = mid ; } else { left = mid + 1 ; } } return left * left == num ; } }

Video Solution

Watch the video walkthrough for Valid Perfect Square

Algorithms:

Binary Search

Patterns:

Math

Companies:

LinkedIn |SAP |