Given a positive integer num, write a function that returns true if num is a perfect square else false.
Note: Do not use the in-built methods to calculate square root or power.
isPerfectSquare(25) => true
isPerfectSquare(30) => falseThe time complexity of the method should be O(log n).
The first line contains 'T' denoting the no. of test cases.
Next T lines each contain a number 'num'.
T lines each contain true or false denoting the answer for each test case.
2
25
30true
false0 <= T <= 105
1 <= N <= 108
Do not look at these unless required.
Think of something similar to how binary search works.
Use binary search to find a number between 1 to n whose square is equal to n.
Solution:
bool searchRoot(int start, int end, int num) {
if (start > end) {
return false;
}
int mid = start + (end - start)/2;
int square = mid*mid;
if (square == num) {
return true;
}
if (square > num) {
return searchRoot(start, mid - 1, num);
}
return searchRoot(mid + 1, end, num);
}
bool isPerfectSquare(num) {
int maxVal = 10000;
return searchRoot(1, maxVal, num);
}Why maxVal?
Because anything beyond that will result in overflow while computing square.