306. Valid Perfect Square
You receive a single positive integer num. Decide whether it is a perfect square — that is, whether some integer x satisfies x * x = num — and return true or false accordingly.
The point of the exercise is to do this with integer arithmetic only: no sqrt, pow, or other built-in root functions (floating-point roots lose precision on large inputs anyway).
Example 1:
Input: num = 16
Output: true
Explanation: 4 × 4 = 16, so 16 is a perfect square.
Example 2:
Input: num = 14
Output: false
Explanation: 3 × 3 = 9 and 4 × 4 = 16 — nothing squares to 14.
Constraints:
- 1 ≤ num ≤ 2³¹ - 1
- Do not use built-in square-root or power functions.
Hints:
Perfect squares are sums of consecutive odd numbers: 1 = 1, 4 = 1+3, 9 = 1+3+5, 16 = 1+3+5+7. Keep subtracting 1, 3, 5, … from num; it is a perfect square exactly when you land on 0. That is O(√num).
The function x → x² is strictly increasing, so 'is there an x with x² = num?' is searchable: binary search x over [1, num], compare mid² to num, and shrink the half that can't contain the root — O(log num).
Watch the arithmetic width: mid² for mid near 46341 overflows 32-bit integers. Use a 64-bit type (or Python's big ints) for the square.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: num = 16
Expected output: true