Valid Perfect Square
Valid Perfect Square: decide whether a positive integer num is the square of an integer, without using any built-in square-root function.
- 1 <= num <= 2³¹ - 1
- You must not use any built-in library function such as sqrt
Intuition
Squaring is increasing on the positive integers: if a < b then a² < b². That makes the sequence of squares sorted, so the candidate root can be binary searched even though no array exists. Each guess mid is tested by comparing mid * mid against num, and the comparison says which half of the remaining range can hold the answer.
Binary search on the answer applies whenever a candidate can be tested for being too small or too large, and that test is monotone. No array is needed — only order and a decisive comparison. Sqrt(x), Koko Eating Bananas, and Split Array Largest Sum are the same technique.
Approach
Before reading on: state why binary search is valid when there is no array to search. Then work out where mid * mid can overflow in a fixed-width language, and how to compare without ever forming the product.
Binary search over an implicit array
There is no array here, yet binary search still applies. What it actually requires is an ordered search space and a test that says which side the answer lies on — and the integers 1..num, keyed by their squares, provide both. This is binary search on the answer: the space being searched is the set of candidate roots, not the input. Once the monotonicity of squaring is stated, the loop is the same one used on a sorted array.
Bounding the search sensibly
Searching 1 to num is correct but wasteful, since for any num > 1 the root is at most num / 2. Either bound works; what matters is that the upper bound is genuinely an over-estimate, so the answer is inside the interval. Use a closed range [1, num] with while lo <= hi, and return false when the interval empties — an empty range means no integer squared to num, so it sits strictly between two consecutive squares.
Comparing without overflow, and why not to use sqrt
Test mid * mid against num directly. In C++ and Java mid * mid can exceed the 32-bit range for large mid, so compute in long or compare mid against num / mid instead. The problem bans sqrt for a real reason beyond exercise: floating-point square roots are approximate, and for large inputs int(sqrt(num)) can land one below the true root, reporting a perfect square as not one. Integer arithmetic has no such failure mode. Time O(log num), space O(1).
Solution & live demo
Common pitfalls
Overflowing the product in C++ or Java
int square = mid * mid;
long square = (long) mid * mid;
With num up to 2³¹ - 1, mid can approach 46341 and mid * mid exceeds the signed 32-bit range, wrapping to a negative value that compares wrongly and sends the search the wrong way.
Trusting a floating-point square root
r = int(sqrt(num)) return r * r == num
binary search on integer products
Beyond the range where doubles represent integers exactly, sqrt can return a value a fraction below the true root, so truncation gives r - 1 and a genuine perfect square is reported as false. It is also explicitly disallowed.
Starting the range at 0
lo, hi = 0, num
lo, hi = 1, num
Zero is not in the valid input range and only adds a wasted iteration whose product is 0. Worse, in variants that divide by mid it introduces a division-by-zero on the very first probe.
Edge cases
The range [1,1] gives mid = 1 and 1 * 1 == 1, so true.
The interval empties between 1 and 2 without a match, so false.
Found in about twenty iterations; the product must not overflow.
Falls strictly between 3² and 4², so the range empties and returns false.
The first midpoint may overshoot, and hi drops until mid = 2 matches.