Code Logo

Valid Perfect Square

Published at24 Jul 2026
Created by
Easy 0 views
Like0

Given a positive integer num, return true if num is a perfect square, or false otherwise. A perfect square is an integer that equals the square of some integer. You may not use any built-in square root functions like sqrt or ** 0.5.

The perfect square test can be solved with binary search between 1 and num. At each step, compute the square of the middle value. If mid * mid == num, it is a perfect square. If the product is less than num, search the right half for a larger candidate. If greater, search the left half.

For the special cases of num = 0 or num = 1, both are perfect squares (0 and 1 respectively), so return true immediately. The product mid * mid can overflow a 32-bit integer for large values of num (up to 231 - 1). In languages with fixed-width integers, use a 64-bit type or compare mid == num / mid to avoid overflow.

Binary search reduces the search space from n to log n comparisons. An O(log n) algorithm is extremely efficient even for the maximum integer value of about 2 billion — only about 31 iterations are needed.

The overflow-safe approach uses division: instead of computing mid*mid, check if mid == num / mid. When mid is the exact square root, both conditions hold. This avoids multiplication overflow for values near the maximum integer limit.

Example Input & Output

Example 1
Input
0
Output
true
Explanation

0*0=0.

Example 2
Input
16
Output
true
Explanation

4*4=16, perfect square.

Example 3
Input
2147395600
Output
true
Explanation

46340*46340=2147395600, large perfect square.

Example 4
Input
1
Output
true
Explanation

1*1=1.

Example 5
Input
14
Output
false
Explanation

No integer squared equals 14.

Algorithm Flow

Recommendation Algorithm Flow for Valid Perfect Square
Recommendation Algorithm Flow for Valid Perfect Square

Solution Approach

Binary search for sqrt. Return true if mid*mid == num, else narrow the range.

function solution(num) {
  if (num < 2) return true;
  var lo = 1, hi = num;
  while (lo <= hi) {
    var mid = Math.floor((lo + hi) / 2);
    var sq = mid * mid;
    if (sq === num) return true;
    if (sq < num) lo = mid + 1;
    else hi = mid - 1;
  }
  return false;
}

Time O(log n), Space O(1).

Best Answers

java
class Solution {
    public boolean solution(int num) {
        if (num < 2) return true;
        int lo = 1, hi = num;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            long sq = (long) mid * mid;
            if (sq == num) return true;
            if (sq < num) lo = mid + 1;
            else hi = mid - 1;
        }
        return false;
    }
}