DSA problem
Valid Perfect Square
Given a positive integer num, return true if num is a perfect square or false otherwise. A perfect square is an integer that is the square of an integer; for example, 1, 4, 9, and 16 are perfect squares while 3, 14, and 26 are not.
You must not use any built-in library function such as sqrt. The intended challenge is to recover the integer square root through pure integer arithmetic, then verify whether squaring it reproduces the input exactly.
The cleanest approach is binary search on the candidate root x over the range [1, num]. The predicate x * x is strictly increasing in x for positive x, so the input is partitioned into three regions: values whose square is below num, possibly one value whose square equals num, and values whose square exceeds num. Binary search locates the boundary.
The one subtle point is overflow: for num up to 2^31 - 1, the candidate mid can reach roughly 46340, so mid * mid fits in a 32-bit integer in many cases — but to be safe across all languages, store mid * mid in a 64-bit long/long long (or compute it as such in TypeScript via Number which handles values up to 2^53 exactly). The search runs in O(log num) time and O(1) space.
Examples
num = 16truenum = 14falsenum = 1trueConstraints
- 1 <= num <= 2^31 - 1
- You must not use the built-in sqrt function.
- The answer must use integer arithmetic only.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.