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.

The catch is that we can't use any built-in square root function. So we need to find another way to determine if 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 around 46,340. That's a manageable search space, which opens the door to both linear and logarithmic approaches.

The key observation is that perfect squares are spaced further and further apart as numbers grow. Between 1 and 100 there are 10 perfect squares, but between 10,000 and 10,100 there might be just one. This spreading-out property means we're searching for a needle in an increasingly sparse haystack, and binary search is a natural fit since the function f(x) = x * x is monotonically increasing.

Key Constraints:

Intuition

The most natural starting point: just try every integer starting from 1 and check if its square equals num. We multiply i * i and compare. If i * i equals num, we found our answer. If i * i exceeds num, we've gone too far and can stop, since squares only get bigger from here.

Think of it like checking a multiplication table one row at a time. You go through 11, 22, 3*3, and so on until you either hit num exactly or overshoot it.

Algorithm

Example Walkthrough

Code

The linear search checks every candidate sequentially through a sorted space. What if we jumped to the middle and eliminated half the candidates in a single comparison?

Intuition

Since perfect squares grow monotonically (1, 4, 9, 16, 25, ...), the function f(x) = x * x is strictly increasing for positive x. This is exactly the property binary search needs. Instead of checking every integer from 1 to sqrt(num), we can search the range [1, num] and halve it at 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 mid * mid is too big, the answer must be in the left half. If mid * mid equals num, we've found it.

One important detail: when computing mid * mid, the result can overflow a 32-bit integer. So we need to use a 64-bit integer (long) for the multiplication.

Algorithm

Example Walkthrough

Code

Binary search is already very efficient, but there's a mathematical approach that converges even faster: Newton's method, which roughly doubles the number of correct digits each iteration.

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 fine) and keep refining. The sequence decreases monotonically toward floor(sqrt(num)) when using integer division. Once it stabilizes, we just check whether the converged value squared equals num.

The beauty of Newton's method is quadratic convergence: the number of correct digits roughly doubles with each iteration. So even for the largest inputs, we converge in about 5-6 steps.

Algorithm

Example Walkthrough

Code