Valid Perfect Square

easy math binary search

Problem

Given a positive integer num, return true if num is a perfect square (some integer r with r*r = num), otherwise false. Do not use any built-in sqrt.

Inputnum = 16

Outputtrue

Binary search r in [1, num]; compare r*r with num.

num

def isPerfectSquare(num):
    lo, hi = 1, num
    while lo <= hi:
        mid = (lo + hi) // 2
        sq = mid * mid
        if sq == num: return True
        if sq < num: lo = mid + 1
        else: hi = mid - 1
    return False

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

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

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

Explanation

We must decide whether num is a perfect square without using any built-in square root. The idea is to guess the root with binary search and check each guess by squaring it.

The root, if it exists, must lie between 1 and num. We keep a window [lo, hi] and test the middle value mid. We compute sq = mid * mid and compare it to num: if they are equal we found a perfect square; if sq is too small we move lo right; if too big we move hi left.

This is correct because squaring is increasing for positive numbers, so a single value of mid tells us which half to discard. If the window empties out without an exact hit, no integer root exists and we return false.

Example: num = 16. Search in [1, 16]. mid = 8 gives 64 > 16 (go left); later mid = 4 gives 16 == 16, so the answer is true. For something like 15, the search would close with no exact match and return false.

Halving the range each step means only about log num guesses are needed.

Time: O(log num) Space: O(1)