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
Valid perfect square tests whether a number is a perfect square, without using any built-in square-root function. That restriction is the point — it forces an actual search or an arithmetic identity.
The binary search approach is the general one. Squares are monotonic, so:
- Search candidate roots from 1 to n / 2, comparing mid × mid against the target — the predicate is monotonic, which is exactly what binary search needs.
The upper bound can be n / 2 for n > 4, since no larger value can square to n, but simply using n is safer and costs one extra iteration.
Overflow is the real hazard: mid × mid exceeds 32-bit range for large inputs. Use 64-bit arithmetic, or compare with mid <= n / mid to avoid multiplying at all.
Newton's method converges faster, iterating x = (x + n / x) / 2 until it stabilises, then checking whether the result squares to n. It reaches the answer in far fewer steps but needs care with integer division.
There is also a neat arithmetic identity worth knowing:
Every perfect square is a sum of consecutive odd numbers — 1, 1+3, 1+3+5 give 1, 4, 9. So repeatedly subtracting successive odd numbers and checking for zero decides the question in O(√n) with only subtraction.
That is slower than binary search but requires no multiplication at all, which occasionally matters.
The boundary cases are 0 and 1, both perfect squares, and both easy to mishandle when the search range starts at 1.
Binary search gives O(log n) time and O(1) space.
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.
Respect the restriction
No built-in square root is allowed, which forces an actual search or an arithmetic identity rather than a library call.
Binary search the root
Squares are monotonic, so search candidate roots comparing mid * mid against n. The monotonic predicate is what makes this valid.
Guard against overflow
mid * mid exceeds 32-bit range for large inputs. Use 64-bit arithmetic, or compare mid <= n / mid to avoid multiplying entirely.
Handle zero and one
Both are perfect squares and both are easy to mishandle when the search range starts at 1. Check them before searching.
Know Newton's method
Iterate x = (x + n / x) / 2 until stable, then verify. Converges in far fewer steps, though integer division needs care.
Know the odd-number identity
Every perfect square is a sum of consecutive odd numbers — 1, 1+3, 1+3+5. Subtracting them until zero or negative decides it in O(√n) with no multiplication.
Cost of the approaches
Binary search is O(log n) time and O(1) space; the odd-number method is O(√n) but avoids multiplication entirely.
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.