🎨Now live: Try our Free AI Image Generation Feature

Description
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.
Intuition
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.
Approach
- Initialize a variable
i
starting from 1 and iterate untili*i
exceedsnum
. - For each value of
i
, check ifi*i
equalsnum
. If it does, returnTrue
asnum
is a perfect square. - If no such
i
is found wherei*i == num
, returnFalse
. - In some languages like C++, ensure that the variable
i
is of typelong long
to prevent overflow.
Complexity
Time Complexity:
O(√n)
- In the worst case, we loop until the square root of
num
.
Space Complexity:
O(1)
- Only a few extra variables are used, so the space complexity is constant.
Code
C++
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;
}
};
Python
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
Java
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;
}
}
JavaScript
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;
};