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.

Example:

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

Approach:

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))

Code:

Output:

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: