Start by applying a binary search between 1 and num to find an integer whose square equals num. Compare mid * mid with num at each step, narrowing the search space. This avoids floating-point errors and ensures correct detection of perfect squares without using library functions.
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.
How GhostInterview Helps
- GhostInterview runs integer-based binary search simulations to verify your perfect square logic in real-time.
- It highlights off-by-one errors in search space adjustments to prevent false negatives or positives.
- The tool explains failure cases where floating-point or overflow errors occur, helping you fix edge cases quickly.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
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.
Need direct help with Valid Perfect Square instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Valid Perfect Square from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Given n, efficiently find the nth digit in the infinite integer sequence using a binary search over valid positions.
Open problem page#441 Arranging CoinsDetermine the maximum number of complete staircase rows possible with n coins using a binary search approach.
Open problem page#268 Missing NumberFind the missing number in an array containing distinct numbers in the range [0, n].
Open problem page