#367

Easy

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Valid Perfect Square

Determine if a given positive integer is a perfect square using a binary search approach over potential square roots efficiently.

math binary search

Problem Statement

You are given a positive integer num. Your task is to return true if num is a perfect square and false otherwise. A perfect square is defined as the square of some integer.

You must solve this without using any built-in square root or power functions. Optimize your approach to handle large inputs efficiently and avoid floating-point inaccuracies.

Examples

Example 1

Input: num = 16

Output: true

We return true because 4 * 4 = 16 and 4 is an integer.

Example 2

Input: num = 14

Output: false

We return false because 3.742 * 3.742 = 14 and 3.742 is not an integer.

Constraints

1 <= num <= 231 - 1

Solution Approach

Binary Search Over Square Roots

Initialize left = 1 and right = num. Repeatedly compute mid = left + (right - left) // 2 and check mid * mid against num. If mid * mid == num, return true. Otherwise, adjust left or right to narrow the search space until left > right.

Edge Case Handling

Directly return true if num is 1 since 1 is a perfect square. Ensure that multiplication does not overflow by using appropriate data types or comparisons before squaring mid.

Avoiding Floating-Point Errors

Do not use sqrt or casting to float. Rely solely on integer arithmetic for comparisons to prevent rounding issues that could incorrectly mark non-perfect squares as true.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(log(num)) because the binary search halves the search space each step. Space complexity is O(1) since only a few variables are needed regardless of input size.

What Interviewers Usually Probe

Confirm the candidate can implement binary search correctly over a numeric range.
Check awareness of integer overflow risks when squaring numbers.
Listen for an approach that avoids floating-point operations for exact perfect square detection.

Common Pitfalls or Variants

Common pitfalls

Attempting to use floating-point sqrt and comparing with rounding, which can fail for large num values.
Forgetting to handle num = 1 as a trivial perfect square.
Squaring mid without checking for overflow, leading to incorrect results or runtime errors.

Follow-up variants

Check if num is a perfect cube using the same binary search over cube roots.
Return all perfect squares less than or equal to num using incremental binary search validation.
Determine if a sequence of numbers contains any perfect squares efficiently using batch binary search.

FAQ

What is the fastest way to check if a number is a perfect square in this problem?

Use binary search over the range 1 to num, comparing mid * mid with num at each step to find an exact integer square root.

Can I use sqrt or other math libraries?

No, built-in functions are prohibited. You must rely on integer arithmetic and binary search to detect perfect squares.

Why not use floating-point comparisons?

Floating-point operations can introduce rounding errors, causing incorrect results for large numbers. Integer arithmetic is precise for this problem.

How do I handle large numbers safely?

Ensure that mid * mid does not overflow by using data types that can store large integers or compare mid with num // mid instead of squaring.

What pattern does this problem follow?

It follows the binary search over valid answer space pattern, testing each candidate integer square root against the target number.

terminal

Solution

Solution 1: Binary Search

We can use binary search to solve this problem. Define the left boundary $l = 1$ and the right boundary $r = num$ of the binary search, then find the smallest integer $x$ that satisfies $x^2 \geq num$ in the range $[l, r]$. Finally, if $x^2 = num$, then $num$ is a perfect square.

1

2

3

4

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        l = bisect_left(range(1, num + 1), num, key=lambda x: x * x) + 1
        return l * l == num

Solution 2: Mathematics

Since $1 + 3 + 5 + \cdots + (2n - 1) = n^2$, we can gradually subtract $1, 3, 5, \cdots$ from $num$. If $num$ finally equals $0$, then $num$ is a perfect square.

1

2

3

4

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        l = bisect_left(range(1, num + 1), num, key=lambda x: x * x) + 1
        return l * l == num

Continue Practicing

#400 nth digit #441 arranging coins #268 missing number