Problem Overview

Given a positive integer num, your task is to determine whether it is a perfect square, without using any math library functions.

A perfect square is any number that can be written as:

x * x

for some integer x.

Examples:

• 16 is valid because 4 * 4 = 16

• 14 is not valid because no integer multiplied by itself equals 14

Approach 1: Simple Loop (O(n))

The direct way is to try all numbers starting from 1:

For each i:

check if i * i == num

If yes → valid
If i * i becomes greater than num, we stop.

This method works but becomes slow when num is very large because you may test millions of values.

Approach 2: Binary Search (O(log n))

Instead of checking all values from 1 to num, we search efficiently in that range.

We assume the integer we are looking for lies somewhere between:

1 and num

Binary search steps:

• Pick the middle value m

• Compute m * m

• Compare it with num

  • If equal → valid

  • If smaller → search in the right half

  • If greater → search in the left half

This reduces the search space drastically and runs very fast even for very large inputs.

Approach 3: Newton’s Method (Faster iterative formula)

This approach repeatedly improves a guess until guess * guess gets close to num.

Although efficient, it is more complex and unnecessary for this problem.
Binary search is simpler and perfectly fits the constraints.

Final Code (Binary Search Approach)

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