How to Check Valid Perfect Square without Sqrt Function?

Given a positive integer num, write a function which returns True if num is a perfect square else False. Note: Do not use any built-in library function such as sqrt.

16 is a perfect square, 14 is not. Without using inbuilt sqrt function we can use a few methods to check.

Bruteforce

Starting from 0 until the number square is bigger than the target. We need to be careful that the square may actually overflow the 32-bit integer thus need to cast it to 64-bit integer e.g. int64_t in C/C++.

class Solution {
public:
    bool isPerfectSquare(int num) {
        for (int i = 0; (int64_t)i * i <= num; ++i) {
            if (i * i == num) return true;
        }
        return false;
    }
};

O(sqrt(n)) time complexity – which is accepted. The above i*i may overflow and multiplication is costly than e.g. subtraction. We can also have the following implementation based on the fact that any perfect square number is in the form of 1+3+5+7+…

class Solution {
public:
    bool isPerfectSquare(int num) {
        if (num < 1) return false;
        for (int i = 1; num > 0; i += 2) {
            num -= i;
        }
        return num == 0;
    }
};

No overflow checks, no multiplcation, but the time complexity is still O(sqrt(n)) although it may actually run a bit faster than the first approach.

Newton Iteration

The Newton Iteration is a mathematic approach that finds optimal answers gradually by approaching. The f'(x) derivative function of x^2 is 2x. Starting at x/2 for the guess of the square root of x, we can approach a better answer by r’=(r+x/r)/2 until the r’^2 is smaller or equal to x.

class Solution {
public:
    bool isPerfectSquare(int num) {
      if (num < 1) return false;
      if (num == 1) return true;
      long t = num / 2;
      while (t * t > num) {
        t = (t + num / t) / 2;
      }
      return t * t == num;        
    }
};

This approach is generally very fast, and a few iterations would yield a very good approximation. Thus the approach runs almost constant time.

Binary Search

As for any sorted integers 1, 2, 3, 4…, its square roots or squares are also sorted, we can thus use binary search algorithm to locate its root in O(logN) which is better than O(sqrt(N)).

class Solution {
public:
    bool isPerfectSquare(int num) {
        if (num < 0) return false;
        if (num <= 1) return true;
        int i = 2;
        int j = num;
        while (i <= j) {
            int64_t  k = i + (j - i) / 2; // avoid integer overflow
            if (k * k == num) return true;
            if (k * k > num) {
                j = k - 1;
            } else {
                i = k + 1;
            }
        }
        return false;
    }
};

This problem is very similar to Integer Sqrt Root except that it does not need computing the actual square root.

–EOF (The Ultimate Computing & Technology Blog) —