Valid Perfect Square Solution

Problem

Given a positive integer, determine whether it is a perfect square — that is, whether some integer multiplied by itself equals it — without using any built-in square root function.

Input: num = 16
Output: true
Explanation: 4 × 4 = 16, so 16 is a perfect square.

Counter-example: num = 14 → false, because no integer satisfies x² = 14.

Intuition

We need to find whether an integer x exists such that x² = num. The sequence of squares 1, 4, 9, 16, 25, … is strictly increasing, so this is really a search problem on a sorted structure. Binary search can eliminate half the remaining candidates at every step, cutting the O(√n) linear scan down to O(log n).

Approach 1 — Linear Scan

Step through candidate integers starting at 1. If the candidate's square matches num, it is a perfect square. Stop as soon as the square exceeds num.

Set candidate to 1.
While candidate² ≤ num, check if candidate² equals num.
If equal, return true.
Otherwise increment candidate and repeat.
If the loop exits without a match, return false.

1def isPerfectSquare(num: int) -> bool:
2    candidate = 1
3    while candidate * candidate <= num:
4        if candidate * candidate == num:
5            return True
6        candidate += 1
7    return False

Time: O(√n) — we test at most √n candidates before the square exceeds num.
Space: O(1) — only a single counter variable.

Approach 2 — Binary Search

Binary search the range [1, num] for an integer whose square equals num. Because squares are monotonically increasing, a comparison tells us exactly which half of the remaining range to keep.

Set left = 1, right = num.
Compute mid = left + (right - left) / 2 to avoid overflow.
Compute square = mid * mid.
If square == num, return true.
If square < num, the answer must lie above mid — set left = mid + 1.
If square > num, the answer must lie below mid — set right = mid - 1.
If the loop ends, no perfect square was found — return false.

1def isPerfectSquare(num: int) -> bool:
2    left, right = 1, num
3    while left <= right:
4        mid = left + (right - left) // 2
5        square = mid * mid
6        if square == num:
7            return True
8        elif square < num:
9            left = mid + 1   # perfect square root must be larger than mid
10        else:
11            right = mid - 1  # perfect square root must be smaller than mid
12    return False

Time: O(log n) — the search space halves on every iteration.
Space: O(1) — a constant number of variables.

Complexity Summary

Approach	Time	Space	When to use
Linear Scan	O(√n)	O(1)	Simple to implement and reason about; fine for small inputs
Binary Search	O(log n)	O(1)	Preferred whenever inputs can be large or O(log n) is required

Common Mistakes

Integer overflow when computing mid * mid in Java or C++: for num near 2³¹ − 1, mid can be around 46,340, and mid * mid overflows a 32-bit int. Declare mid and the product as long.
Using (left + right) / 2 instead of left + (right - left) / 2: the sum left + right can itself overflow when both values are large; the safer form avoids this.
Condition left < right instead of left <= right: when the answer sits at the position where left == right, the stricter condition exits the loop one iteration early and incorrectly returns false.
Starting the linear scan at 0: 0 * 0 == 0 creates a false positive for num = 0, and the problem guarantees num ≥ 1, so 1 is the correct starting point.
Forgetting that num = 1 is a valid perfect square: 1 = 1², so any logic that starts checking from 2 or uses a strict < comparison in the loop will mishandle this boundary case.

Valid Perfect Square — Solution