Valid Perfect Square

Easy
57.

Valid Perfect Square

Valid Perfect Square is an easy coding problem on math and binary search, asked in HCL interviews.

Given a positive integer num, return true if it is a perfect square (an integer times itself), without using any built-in sqrt function.

Example 1

Input
num = 16
Output
true
Explanation
4 × 4 = 16.

Example 2

Input
num = 14
Output
false

Constraints

  • 1 <= num <= 2147483647
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} num
 * @return {boolean}
 */
var isPerfectSquare = function(num) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Valid Perfect Square — Solution in Python, Java & C++

Valid Perfect Square solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at HCL.

Valid Perfect Square is an easy coding problem on math and binary search, asked in HCL interviews.

  • Difficulty: Easy
  • Topics: Math, Binary Search
  • Asked at: HCL
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given a positive integer num, return true if it is a perfect square (an integer times itself), without using any built-in sqrt function.

Example 1

Input: num = 16
Output: true
Explanation: 4 × 4 = 16.

Example 2

Input: num = 14
Output: false

Constraints

  • 1 <= num <= 2147483647

Hints for Valid Perfect Square

  1. Hint 1

    Binary search k in [1, num] on k*k versus num.

  2. Hint 2

    Newton's method converges even faster: k = (k + num/k) / 2.

How to solve Valid Perfect Square

Same monotone answer-space search as integer square root, but the question is exact: does some integer k satisfy k * k == num? Binary search k, comparing without ever forming the product so nothing overflows.

Approach

  1. Search k in [1, num].
  2. For each mid, compute the quotient q = num / mid and remainder r = num % mid.
  3. If q == mid and r == 0, then mid * mid == num exactly — return true.
  4. If q > mid, then mid is too small — search higher; otherwise search lower.
  5. An exhausted range means no such integer exists.

Why it works

num / mid compared against mid reproduces the ordering of mid * mid against num without multiplying: quotient greater than mid means the square is short of num, quotient smaller means it overshoots. Equality of the quotient plus a zero remainder is precisely divisibility with matching factors, i.e. an exact square. The comparison is monotone in mid, so binary search applies.

Complexity

  • Time — O(log num)
  • Space — O(1)

Pitfalls

  • mid * mid overflows a 32-bit integer for inputs near 2.1 billion — this is the whole reason for the division form.
  • The remainder check matters: num / mid == mid alone is true for num = 8, mid = 2 (8 / 2 == 2) even though 8 is not a square.
  • Built-in sqrt is disallowed, and floating point is unreliable at this magnitude regardless.
  • Start the range at 1, not 0, so the division is always safe.

Reference solution

Python

def isPerfectSquare(num: int) -> bool:
    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

Java

public static boolean isPerfectSquare(int num) {
    int lo = 1, hi = num;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int q = num / mid;
        int r = num % mid;
        if (q == mid && r == 0) return true;
        if (q > mid) lo = mid + 1;
        else hi = mid - 1;
    }
    return false;
}

C++

bool isPerfectSquare(int num) {
    int lo = 1, hi = num;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int q = num / mid;
        int r = num % mid;
        if (q == mid && r == 0) return true;
        if (q > mid) lo = mid + 1;
        else hi = mid - 1;
    }
    return false;
}

JavaScript

var isPerfectSquare = function(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;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue

Learn the technique: Binary Search