EasyMathBinary Search

Valid Perfect Square

2 approaches, code in every language

Given a positive integer, decide whether it is a perfect square, meaning it equals some whole number multiplied by itself. Return true when such a whole number exists and false otherwise.

The catch is that built-in square-root helpers are not allowed, so you must determine the answer using arithmetic and a search of your own.

Example 1

Input: num = 16

Output: true

16 is 4 times 4, so it is a perfect square.

Example 2

Input: num = 14

Output: false

No whole number squared gives 14, so the answer is false.

Constraints

1 ≤ num ≤ 2^31 - 1
You may not use any built-in square root function

Binary Search on the Root

Search the range of possible roots and check whether any candidate squared equals the number.

Loading animation…

Intuition

If the number has an integer square root, that root lies somewhere between 1 and the number itself. Because squaring is monotonic over positive integers, we can binary search for the root: compare a candidate squared against the target and shrink the search window based on whether it overshot or fell short. Widening the intermediate value to a 64-bit type avoids overflow when squaring near the upper limit.

Algorithm walkthrough

1Set lo to 1 and hi to num as the inclusive bounds for the root.
2While lo does not exceed hi, take the midpoint and square it.
3If the square equals num, the number is a perfect square, so return true.
4If the square is too small, raise lo above mid; if too large, lower hi below mid.
5If the window empties without a match, return false.

Implementation

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        lo, hi = 1, num
        while lo <= hi:
            mid = (lo + hi) // 2
            sq = mid * mid
            if sq == num:
                return True
            elif sq < num:
                lo = mid + 1
            else:
                hi = mid - 1
        return False

Time

O(log n)

Space

O(1)

Newton's Method

Iteratively refine a guess for the root using integer Newton iteration, then verify the square.

Loading animation…

Intuition

Newton's method for square roots repeatedly replaces a guess x with the average of x and num/x, which converges very quickly toward the true root. Doing this in integer arithmetic drives x down to the floor of the square root; once it settles, squaring that value and comparing to the original number confirms whether the number was a perfect square.

Algorithm walkthrough

1Start with a guess x equal to num.
2While x squared still exceeds num, update x to the integer average of x and num divided by x.
3The loop lowers x until it reaches the floor of the square root.
4Return true only if that final x squared exactly matches num.

Implementation

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        x = num
        while x * x > num:
            x = (x + num // x) // 2
        return x * x == num

Time

O(log n)

Space

O(1)

Newton iteration converges quadratically, so it reaches the root in few steps.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Search

After the pattern

Now solve one you haven't seen.

Square Crate Block is our own problem on the technique behind Valid Perfect Square: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free