Valid Perfect Square
Given a positive integer numtruefalseMath.sqrt
Example 1
Output: true
Explanation: 4 × 4 = 16.
Example 2
Output: false
Explanation: 3 × 3 = 9 and 4 × 4 = 16, so no integer squares to 14.
How to Think About It
Step 1: Look for an exact value
The question is whether some integer rnumr × r == numr
Step 2: Compare the square of the middle
- If
: it is a perfect square.mid × mid == num - If
: the root, if there is one, is bigger:mid × mid < num .lo = mid + 1 - If
: it is smaller:mid × mid > num .hi = mid - 1 - If the range becomes empty, no integer squares to
.num
Step 3: Use long for the square
nummidmid × midintlong
Walkthrough
num = 14:
| lo | hi | mid | mid × mid | Decision |
|---|---|---|---|---|
| 1 | 14 | 7 | 49 | too big, hi = 6 |
| 1 | 6 | 3 | 9 | too small, lo = 4 |
| 4 | 6 | 5 | 25 | too big, hi = 4 |
| 4 | 4 | 4 | 16 | too big, hi = 3 |
The range is empty: 14 lies between 3 × 3 and 4 × 4, so it is not a perfect square.
Java Solution
This is the exact-match template, searching for a number whose square equals num
public class ValidPerfectSquare {
public static boolean isPerfectSquare(int num) {
long lo = 1;
long hi = num;
while (lo <= hi) {
long mid = lo + (hi - lo) / 2;
long square = mid * mid; // long, so the square cannot overflow
if (square == num) {
return true;
} else if (square < num) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return false; // no integer squares to num
}
public static void main(String[] args) {
System.out.println(isPerfectSquare(16)); // true
System.out.println(isPerfectSquare(14)); // false
System.out.println(isPerfectSquare(2147483647)); // false
}
}
The original implementation, num
Complexity
- Time: O(log n).
- Space: O(1).