Code Logo

Valid Perfect Square

Published at24 Jul 2026
Created by
Easy 1 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

Solution Approach

Check if a number is a perfect square without using the built-in sqrt function. Use binary search on the range [1, num] to find an integer whose square equals num. At each step, compute mid and compare mid*mid with num. If mid*mid equals num, return true. If mid*mid is too large, search the left half; if too small, search the right half.

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

Binary search narrows the candidate range by half each iteration. For num=16, the search narrows from [1,16] to [1,8] to [5,8] to [5,6] to [4,4] where 4*4=16 matches. Handle num=0 and num=1 as edge cases.

Time complexity is O(log n), space complexity is 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;
    }
}