Sponsored
Sponsored
The binary search method utilizes the principle that for a number n to be a perfect square, there exists an integer x such that x * x = n. By searching between 1 and n, binary search will narrow down the possibilities by checking the middle value, squaring it, and adjusting the search range based on whether the squared value is less than, greater than, or equal to n. This ensures a time complexity of O(log n).
Time Complexity: O(log n)
Space Complexity: O(1)
1class Solution {
2 public boolean isPerfectSquare(int num) {
3 long left = 1, right = num;
4 while (left <= right) {
5 long mid = left + (right - left) / 2;
6 long square = mid * mid;
7 if (square == num) return true;
8 if (square < num) left = mid + 1;
9 else right = mid - 1;
10 }
11 return false;
12 }
13}Java uses long to handle large values safely, and implements the binary search logic, efficiently narrowing down to the probable integer square root if any.
Newton's method is an iterative numerical approach to approximate solutions to functions. For finding a square root, the function is designed around n = x^2. By iteratively refining the guess x using x = (x + n/x) / 2, the method converges to an integer square root if one exists. This method can be faster than binary search with careful tuning.
Time Complexity: O(log n)
Space Complexity: O(1)
1public:
bool isPerfectSquare(int num) {
if (num < 2) return true;
long x = num / 2;
while (x * x > num) {
x = (x + num / x) / 2;
}
return x * x == num;
}
};Similar to C, this C++ solution uses Newton's method, iterating the guess by polynomial convergence to reach a possible integer square.