Scale Engineer

Valid Perfect Square

Easy
#0354Time: O(sqrt(n)), where n is the input number `num`. In the worst case, we iterate from 1 up to `sqrt(num)`.Space: O(1), as we only use a constant amount of extra space for the loop variable.2 companies
Patterns
Math
Algorithms
Binary Search
Companies
LinkedInSAP

Prompt

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 <= 231 - 1

Approaches

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

O(sqrt(n)), where n is the input number `num`. In the worst case, we iterate from 1 up to `sqrt(num)`.

Space

O(1), as we only use a constant amount of extra space for the loop variable.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem