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