Valid Perfect Square - Solution & Explanation
Problem Statement
Given a positive integer num, return true if num is a perfect square or false otherwise.
A perfect square is an integer that is the square of an integer. In other words, it is the product of some integer with itself.
You must not use any built-in library function, such as sqrt.
Example 1:
Input: num = 16 Output: true Explanation: We return true because 4 * 4 = 16 and 4 is an integer.
Example 2:
Input: num = 14 Output: false Explanation: We return false because 3.742 * 3.742 = 14 and 3.742 is not an integer.
Constraints:
1 <= num <= 231 - 1
Approach Overview
Problem Overview: You receive a positive integer num. The task is to determine whether it is a perfect square without calling built-in square root functions such as sqrt(). A number is a perfect square if some integer x satisfies x * x = num.
Approach 1: Binary Search (O(log n) time, O(1) space)
This problem fits naturally with binary search. Any perfect square x² that equals num must have x between 1 and num. Search this range and repeatedly test the midpoint. Compute mid * mid and compare it with num. If the square is equal, you found the integer root. If it is smaller, move the left boundary to mid + 1. If it is larger, move the right boundary to mid - 1. Each iteration cuts the search range in half, which gives O(log n) time complexity. The algorithm stores only a few integer variables, so the space complexity stays O(1). This approach is reliable and avoids floating-point precision issues.
Careful handling of multiplication prevents overflow in languages with fixed integer sizes. Using mid <= num / mid instead of mid * mid <= num avoids exceeding integer limits in C++ or Java. This pattern appears frequently in integer square root problems and is common in interview settings when math constraints are involved.
Approach 2: Newton's Iteration Method (O(log n) time, O(1) space)
Newton's method computes square roots using iterative approximation. Start with an initial guess x = num. Repeatedly update it using the formula x = (x + num / x) / 2. Each iteration rapidly converges toward the integer square root. Stop when x * x <= num. If the final value squared equals num, the number is a perfect square.
The key advantage is fast convergence. Newton's method reduces the error exponentially, so the number of iterations is roughly O(log n) but usually much smaller in practice. The algorithm uses only integer variables, keeping space complexity at O(1). This method is common in numerical computing and sometimes appears in interviews that test deeper math intuition.
Recommended for interviews: Binary search is the most expected solution. It demonstrates control over search boundaries, integer overflow handling, and logarithmic reasoning. Newton's method is an excellent follow-up optimization that shows mathematical insight. Many candidates first present binary search to establish correctness, then discuss Newton's iteration as a faster numerical approach.
Approach 1: Binary Search Approach
The binary search method utilizes the principle that for a number n to be a perfect square, there exists an integer x such that x * x = n. By searching between 1 and n, binary search will narrow down the possibilities by checking the middle value, squaring it, and adjusting the search range based on whether the squared value is less than, greater than, or equal to n. This ensures a time complexity of O(log n).
The C implementation uses two pointers, left and right, to represent the range of potential roots. The mid value is checked if its square equals the input number. The range is adjusted by moving the left or right pointer, eventually finding the square or exhausting possibilities.
Complexity
Time Complexity: O(log n)
Space Complexity: O(1)
Approach 2: Newton's Iteration Method
Newton's method is an iterative numerical approach to approximate solutions to functions. For finding a square root, the function is designed around n = x^2. By iteratively refining the guess x using x = (x + n/x) / 2, the method converges to an integer square root if one exists. This method can be faster than binary search with careful tuning.
Starts with an initial guess and iteratively applies Newton's formula to converge the guess to the correct number, utilizing standard while and arithmetic operations.
Complexity
Time Complexity: O(log n)
Space Complexity: O(1)
Approach 3: 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.
The time complexity is O(log n), where n is the given number. The space complexity is O(1).
Approach 4: 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.
The time complexity is O(\sqrt n), and the space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Binary Search Approach | Time Complexity: O(log n) |
| Newton's Iteration Method | Time Complexity: O(log n) |
| Binary Search | — |
| Mathematics | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Binary Search | O(log n) | O(1) | General case when checking if an integer square root exists without using built-in functions |
| Newton's Iteration Method | O(log n) | O(1) | When you want faster convergence and a math-based optimization for square root calculation |
Video Solution
Valid Perfect Square - Leetcode 367 - Python • NeetCode • 45,193 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Valid Perfect Square easy or hard?
How to solve Valid Perfect Square in O(log n)?
What is the best approach for Valid Perfect Square?
What data structure is used in Valid Perfect Square?
What is the time complexity of Valid Perfect Square?
Valid Perfect Square Python or Java solution approach?
Is Valid Perfect Square asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Valid Perfect Square with our built-in code editor and test cases.
Practice on FleetCode