Valid Perfect Square

Problem

Given a positive integer num, return true if num is a perfect square or false otherwise.

A perfect square is an integer that is the square of an integer. In other words, it is the product of some integer with itself.

You must not use any built-in library function, such as sqrt.

Constraints

• 1 <= num <= 231 - 1

Solution

The problem Valid Perfect Square can be solved using Heron’s method. According to Heron’s method, approximation of a square root can be computed using the following process.

Based on the equation above, following equation also holds true for xk >= sqrt(S).

Therefore, by first setting the initial approximate to sqrt(INT_MAX) and repeating the process while rounding down the approximate until square of the approximate goes below given number, it is possible too check if a given number is a perfect square.

Implementation

class Solution
{
  public:
    bool isPerfectSquare(int num)
    {
        double est = 46341;
        while (est * est > num)
            est = (int)(est + num / est) / 2;

        return est * est == num;
    }
};