Reference: LeetCode EPI 11.4
Difficulty: Easy

Problem

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Note: Do not use any built-in library function such as sqrt.

Example:

1

Follow up:

Analysis

Brute-Force & Cheating

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// brute-force
public boolean isPerfectSquare(int num) {
for (int i = 1; i <= num; ++i) {
if (i * i == num) {
return true;
}
}
return false;
}

// cheating
public boolean isPerfectSquare(int num) {
int x = (int) Math.sqrt(num);
return x * x == num;
}

Time: $O(N)$ for brute-force.
Space: $O(1)$

Standard Version:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean isPerfectSquare(int num) {
int lo = 1, hi = num;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (mid * mid == num) {
return true;
}
if (mid > num / mid) {
hi = mid - 1;
} else {
lo = mid + 1;
}
}
return false;
}

Other Version:

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean isPerfectSquare(int num) {
int lo = 1, hi = num;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (mid >= num / mid) {
hi = mid - 1;
} else {
lo = mid + 1;
}
}
// check
return (lo * lo == num);
}

Time: $O(\log{N})$
Space: $O(1)$


Comment