Dare2Solve
The problem is to determine whether a given number num
is a perfect square. A perfect square is an integer that is the square of an integer. For example, 16 is a perfect square because 4 × 4 = 16, but 20 is not a perfect square because there is no integer that squares to 20.
A brute force approach would be to try every number from 1 to num
and check if its square equals num
. This approach can be inefficient for large numbers, so instead, we can limit the number of checks by iterating up to sqrt(num)
.
To avoid overflow issues (which exist in certain programming languages like C++), we handle the multiplication carefully. In languages like Python, there's no risk of overflow due to the dynamic nature of integer types.
i
starting from 1 and iterate until i*i
exceeds num
.i
, check if i*i
equals num
. If it does, return True
as num
is a perfect square.i
is found where i*i == num
, return False
.i
is of type long long
to prevent overflow.O(√n)
num
.O(1)
class Solution {
public:
bool isPerfectSquare(int num) {
long long q = num / 4; // Use long long to avoid overflow
long long i = 1; // Use long long for i as well
while (i * i <= num) { // Check if i*i exceeds num to avoid overflow
if (i * i == num) {
return true;
} else {
i++;
}
}
return false;
}
};
class Solution:
def isPerfectSquare(self, num: int) -> bool:
q = num // 4 # Integer division in Python
i = 1
while i * i <= num: # Check if i*i exceeds num
if i * i == num:
return True
i += 1
return False
class Solution {
public boolean isPerfectSquare(int num) {
int q = num / 4;
int i = 1;
while (i <= q + 1) {
if (i * i == num) {
return true;
} else {
i++;
}
}
return false;
}
}
var isPerfectSquare = function (num) {
let q = Math.floor(num / 4);
let i = 1;
while (i <= q + 1) {
if (i * i == num) {
return true;
}
else {
i++;
}
}
return false;
};