AlgoMaster Logo

Valid Perfect Square

easy7 min readUpdated June 23, 2026

Understanding the Problem

We need to figure out whether a given positive integer is the square of some other integer. For example, 1, 4, 9, 16, 25 are all perfect squares because they equal 1^2, 2^2, 3^2, 4^2, 5^2, respectively. Numbers like 2, 3, 5, 14 are not.

We can't use any built-in square root function, so we need another way to determine whether there exists an integer x such that x * x == num. The input can be as large as 2^31 - 1 (about 2.1 billion), so the square root could be up to about 46,340. That bounds the search space and allows both linear and logarithmic approaches.

The function f(x) = x * x is strictly increasing for positive x. That monotonic property is what makes binary search applicable here: a single comparison of mid * mid against num tells us which half of the range can still contain the answer.

Key Constraints:

  • 1 <= num <= 2^31 - 1 → The input is always positive, so there is no zero or negative case to handle. The maximum is about 2.1 billion, so its square root is at most about 46,340. That rules out anything worse than a linear scan and makes binary search trivially fast (about 31 iterations).
  • num near 2^31 - 1 → Candidate squares can exceed the 32-bit signed range. Any product like mid * mid must be computed in 64-bit arithmetic to avoid overflow.
  • No built-in sqrt allowed → We must implement our own search or numerical method.

Approach 1: Linear Search

Intuition

Try every integer starting from 1 and check whether its square equals num. Compute i * i and compare. If i * i equals num, the answer is true. If i * i exceeds num, we can stop: squares only grow from here, so no larger i can match.

This walks through 11, 22, 3*3, and so on until it either hits num exactly or overshoots it.

Algorithm

  1. Start with i = 1.
  2. While i * i is less than or equal to num:
    • If i * i == num, return true.
    • Increment i.
  3. If the loop ends without finding a match, return false.

Example Walkthrough

1Start: i=1, check 1*1=1, not 16, continue
0
1
i=1, 1*1=1
1
2
2
3
3
4
4
5
1/4

Code

Linear search checks candidates one at a time through a sorted space. Since that space is sorted by value, binary search can eliminate half of it per comparison.

Approach 2: Binary Search

Intuition

Because f(x) = x * x is strictly increasing for positive x, the candidate range [1, num] is sorted by square value. That lets binary search replace the linear scan: instead of testing every integer up to sqrt(num), we halve the range each step.

Pick a midpoint, compute its square, and compare to num. If mid * mid is too small, the answer must be in the right half. If it is too big, the answer must be in the left half. If it equals num, we found it.

One detail matters: mid * mid can exceed the 32-bit signed range when num is near 2^31 - 1, so the multiplication uses a 64-bit integer (long).

The discard step is safe in both directions. If mid * mid < num, then for every value v < mid we have v * v < mid * mid < num, so the entire left half is too small and can be dropped. If mid * mid > num, the same argument rules out everything to the right of mid. Each step removes half the range, so the search ends in O(log n) steps with either a match or an empty range.

Algorithm

  1. Set left = 1 and right = num.
  2. While left <= right:
    • Compute mid = left + (right - left) / 2.
    • Compute square = mid * mid using 64-bit arithmetic.
    • If square == num, return true.
    • If square < num, set left = mid + 1.
    • If square > num, set right = mid - 1.
  3. If the loop ends without finding a match, return false.

Example Walkthrough

1Initial range [1, 16], mid = 8
0
1
left
1
2
2
3
3
4
4
5
5
6
6
7
7
mid=8
8
8
9
9
10
10
11
11
12
12
13
13
14
14
15
15
16
right
search range
1/4

Code

Binary search halves the range each step. A numerical method converges faster: Newton's method roughly doubles the number of correct digits per iteration.

Approach 3: Newton's Method

Intuition

Newton's method is a classic numerical technique for finding roots of equations. We want to find x where x^2 = num, which is equivalent to finding the root of f(x) = x^2 - num. The update rule simplifies to:

x_next = (x + num / x) / 2

This is the same formula known as the "Babylonian method" for computing square roots. We start with an initial guess (num itself works) and keep refining. With integer division, the sequence decreases monotonically until it reaches floor(sqrt(num)) and stabilizes. We then check whether that value squared equals num.

Newton's method has quadratic convergence: the number of correct digits roughly doubles per iteration, so even the largest inputs settle in about 5-6 steps.

Each update x = (x + num/x) / 2 is the arithmetic mean of x and num/x. When x overshoots the true root (x > sqrt(num)), num/x undershoots it, so their average sits between them and closer to the root. The loop condition x * x > num stops exactly when x has descended to floor(sqrt(num)), and the final x * x == num check distinguishes a perfect square from a value whose floor-root rounds down.

Algorithm

  1. Start with x = num.
  2. While x * x > num:
    • Update x = (x + num / x) / 2 using integer division.
  3. Return true if x * x == num, otherwise false.

Example Walkthrough

1Start: x = 16, x*x = 256 > 16
16
x=16
8
5
4
1/4

Code