Valid Perfect Square
Decide whether a number is a perfect square without sqrt by binary searching for a whole k whose square equals it.
Problem Understanding
Valid Perfect Square: given a positive integer num, return true if it is the square of an integer, without using a built-in square root.
Example: 16 returns true (4²); 14 returns false.
The Intuition: Squares Are Sorted
The squares 1, 4, 9, 16, … increase with k, so finding a k with k² == num is a search in a sorted sequence, which is exactly what binary search does:
- Search
kin[1, num]. mid² == num: found it.mid² < num: the root is to the right.mid² > num: the root is to the left.
It is the exact-match sibling of Sqrt(x), which instead keeps the largest k with k² ≤ x.
Interactive Walkthrough
Every candidate k is shown with k² underneath; the range [lo, hi] is tinted and mid is filled. Try Example 2 to watch the range empty when num falls between two squares.
Dry Run Table
Input: num = 14
| lo | hi | mid | mid² | Move |
|---|---|---|---|---|
| 1 | 14 | 7 | 49 | > 14: hi = 6 |
| 1 | 6 | 3 | 9 | < 14: lo = 4 |
| 4 | 6 | 5 | 25 | > 14: hi = 4 |
| 4 | 4 | 4 | 16 | > 14: hi = 3 |
lo = 4 > hi = 3. Answer: false.
The Solution Template
Exact-match binary search on k. Java, C++ and C square in 64 bits.
Valid Perfect Square Code
1var isPerfectSquare = function(num) {2 let lo = 1, hi = num;3 while (lo <= hi) {4 const mid = Math.floor((lo + hi) / 2), sq = mid * mid;5 if (sq === num) return true;6 if (sq < num) lo = mid + 1;7 else hi = mid - 1;8 }9 return false;10};
Edge Cases & Common Mistakes
- num = 1: 1² = 1; the first mid finds it.
- Overflow: for num near 2³¹ − 1,
mid * midoverflows 32-bit ints; use 64-bit values. - Floating point:
int(num ** 0.5) ** 2 == numcan be wrong for very large values because of rounding. - Using
lo < hi: with exact-match search,lo <= hiis needed so the last candidate is checked. - Tighter bound: for num ≥ 4 the root is at most num / 2, which saves one step but is not required.
Summary
Binary search k in [1, num]: an exact square returns true, a smaller square moves lo up, a bigger one moves hi down, and an empty range returns false. Use 64-bit math for the square. O(log num) time and O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet