Is Perfect Square Editorial

Practice Problem Link: Is Perfect Square | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a positive integer num, write a function that returns true if num is a perfect square else return false.

Naive Approach

A simple way to solve this problem is to run a loop from i = 1 to i = n and as soon as i * i is greater than equal to n break the loop. If i * i is equal to n at some point return true otherwise return false. 

Analysis

• Time Complexity: O(sqrt(n))
• Space Complexity: O(1)

Implementation

C++

bool isPerfectSquare(int num) {
   for (int i = 1; i <= num; i++) {
       if (i * i == num) {
           return true;
       } else if (i * i > num) {
           return false;
       }
   }
}

Java

class Solution {
   boolean isPerfectSquare (int num) {
       for (int i = 1; i <= num; i++) {
           if (i * i == num) {
               return true;
           } else if (i * i > num) {
               return false;
           }
       }
       return false;
   }
}

Optimal Approach

The problem can be solved by using the concept of binary search from 1 to n to find a value whose square is equal to n.

• Declare three variables low=1(lower bound) and high=n(upper bound), mid.
• Perform a binary search until (low<=high).
• Initialize mid=(low+high)/2 and check if the square of mid is equal to n, return true. Otherwise, if the square of mid is less than n, search in the second half else search in the first half.
• Return false as the default condition.

Analysis

• Time Complexity: O(log(n))
• Space Complexity: O(1)

Implementation

C++

bool searchRoot(int low, int high, int num) {
   if (high >= low) {
       int mid = (high + low) / 2;
       int square = mid * mid;
       if (square == num) {
           return true;
       } else if (square > num) {
           return searchRoot(low, mid - 1, num);
       } else {
           return searchRoot(mid + 1, high, num);
       }
   }
   return false;
}
bool isPerfectSquare(int num) {
   int maxVal = 10000; // To avoid overflow while computing square
   return searchRoot(1, maxVal, num);
}

Java

class Solution {
   boolean searchRoot(int low, int high, int num) {
       if (high >= low) {
           int mid = (high + low) / 2;
           int square = mid * mid;
           if (square == num) {
               return true;
           } else if (square > num) {
               return searchRoot(low, mid - 1, num);
           } else {
               return searchRoot(mid + 1, high, num);
           }
       }
       return false;
   }
   boolean isPerfectSquare (int num) {
       int maxVal = 10000;
       return searchRoot(1, maxVal, num);
   }
}