Problem: Check if a given positive integer is a perfect square or not without using any built-in library function such as sqrt.
Example:
Input: num = 81 Output: true
Approach: We can use binary search with say low = 2 and high = num but do we really need to search till num? I think not. If you see for any num > 1, the square root of the num will always be less than or equal to num / 2 so we can take num/2 as high.
But there is still problem here which is while doing binary search when we will compare mid * mid to the num, mid * mid might overflow the max limit of int and that will create a problem. How to resolve this issue?
Let's see what is the maximum value a int can take; It is 2147483647. What is the square root of this number; 46,340.95... That means there is can't be a int value which is a perfect square and whose square root is more than 46,340, right! Given this fact we can always take high as 46,340.
That's it.
Implementation in C#:
public static bool IsPerfectSquareWithoutSqrt(int num)
{
if (num == 1)
{
return true;
}
int low = 2, high = num / 2 > 46340 ? 46340 : num / 2;
while (low <= high)
{
int mid = low + (high - low) / 2;
int sqr = mid * mid;
if (num == sqr)
{
return true;
}
else if (sqr < 0 || num < sqr)
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
return false;
}
Complexity: O(logn)
No comments:
Post a Comment