Description
Given a positive integer num, return true if num is a perfect square or false otherwise.
A perfect square is an integer that is the square of an integer. In other words, it is the product of some integer with itself.
You must not use any built-in library function, such as sqrt.
Example 1:
Input: num = 16
Output: true
Explanation: We return true because 4 * 4 = 16 and 4 is an integer.
Example 2:
Input: num = 14
Output: false
Explanation: We return false because 3.742 * 3.742 = 14 and 3.742 is not an integer.
Constraints:
Solutions
Solution 1: Binary Search
We can use binary search to solve this problem. Define the left boundary l = 1 and the right boundary r = num of the binary search, then find the smallest integer x that satisfies x^2 ≥ num in the range [l, r]. Finally, if x^2 = num, then num is a perfect square.
The time complexity is O(log n), where n is the given number. The space complexity is O(1).
PythonJavaC++GoTypeScriptRust
class Solution:
def isPerfectSquare(self, num: int) -> bool:
l = bisect_left(range(1, num + 1), num, key=lambda x: x * x) + 1
return l * l == num(code-box)
class Solution {
public boolean isPerfectSquare(int num) {
int l = 1, r = num;
while (l < r) {
int mid = (l + r) >>> 1;
if (1L * mid * mid >= num) {
r = mid;
} else {
l = mid + 1;
}
}
return l * l == num;
}
}(code-box)
class Solution {
public:
bool isPerfectSquare(int num) {
int l = 1, r = num;
while (l < r) {
int mid = l + (r - l) / 2;
if (1LL * mid * mid >= num) {
r = mid;
} else {
l = mid + 1;
}
}
return 1LL * l * l == num;
}
};(code-box)
func isPerfectSquare(num int) bool {
l := sort.Search(num, func(i int) bool { return i*i >= num })
return l*l == num
}(code-box)
function isPerfectSquare(num: number): boolean {
let [l, r] = [1, num];
while (l < r) {
const mid = (l + r) >> 1;
if (mid >= num / mid) {
r = mid;
} else {
l = mid + 1;
}
}
return l * l === num;
}(code-box)
impl Solution {
pub fn is_perfect_square(num: i32) -> bool {
let mut l = 1;
let mut r = num as i64;
while l < r {
let mid = (l + r) / 2;
if mid * mid >= (num as i64) {
r = mid;
} else {
l = mid + 1;
}
}
l * l == (num as i64)
}
}(code-box)
Solution 2: Mathematics
Since 1 + 3 + 5 + … + (2n - 1) = n^2, we can gradually subtract 1, 3, 5, … from num. If num finally equals 0, then num is a perfect square.
The time complexity is O(\sqrt n), and the space complexity is O(1).
PythonJavaC++GoTypeScriptRust
class Solution:
def isPerfectSquare(self, num: int) -> bool:
i = 1
while num > 0:
num -= i
i += 2
return num == 0(code-box)
class Solution {
public boolean isPerfectSquare(int num) {
for (int i = 1; num > 0; i += 2) {
num -= i;
}
return num == 0;
}
}(code-box)
class Solution {
public:
bool isPerfectSquare(int num) {
for (int i = 1; num > 0; i += 2) {
num -= i;
}
return num == 0;
}
};(code-box)
func isPerfectSquare(num int) bool {
for i := 1; num > 0; i += 2 {
num -= i
}
return num == 0
}(code-box)
function isPerfectSquare(num: number): boolean {
let i = 1;
while (num > 0) {
num -= i;
i += 2;
}
return num === 0;
}(code-box)
impl Solution {
pub fn is_perfect_square(mut num: i32) -> bool {
let mut i = 1;
while num > 0 {
num -= i;
i += 2;
}
num == 0
}
}(code-box)
