Check if given number is perfect square – O(√N) Solution

Objective: Given a number, write a program to check if given number is perfect sqaure.


N = 16
Output: True
N = 32
Output: False


Naive Approach:

  • If N = 1 return true.
  • Iterate through 1 to N/2 and check for each number whether square of each number is equal to N, if yes then return true, else false.

Time Complexity: O(N/2)

Better Approach:

Initialize left = 0, right = N, and find mid = (left+right)/2;
Check if N%mid=0 && mid*mid = N then N is perfect square.
else if(mid<num/mid) then left = mid+1;
else right = mid-1;

Time Complexity: O(√N))



16 is perfect square: true
32 is perfect square: false

Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.

You may also like...

%d bloggers like this: