Be the first user to complete this post

  • 0
 Add to List
Beginner

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

Output:

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

Related Problems: