Valid Perfect Square
EasyPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach iterates through numbers from 1 up to num and checks if the square of any number i equals num. To optimize, we only need to iterate as long as i * i <= num.
Algorithm
- Initialize a
longvariableito 1. - Loop as long as the square of
iis less than or equal tonum. - Inside the loop, check if
i * iis equal tonum. - If it is, return
true. - If the loop finishes without finding such an
i, it meansnumis not a perfect square, so returnfalse.
Walkthrough
The most straightforward method is to check every integer i starting from 1 to see if its square is equal to the given number num.
We can start a loop with a counter i (as a long to prevent overflow when squaring) from 1.
In each iteration, we calculate the square of i.
- If
i * iequalsnum, we have found an integer whose square isnum, sonumis a perfect square, and we can returntrue. - If
i * iexceedsnum, it means that the square ofiand any subsequent integer will also be greater thannum. Therefore,numcannot be a perfect square, and we can stop the search and returnfalse.
This method is simple but can be slow for very large values of num.
class Solution { public boolean isPerfectSquare(int num) { if (num < 1) return false; if (num == 1) return true; for (long i = 1; i * i <= num; i++) { if (i * i == num) { return true; } } return false; }}Complexity
Time
O(sqrt(n)), where n is the input number `num`. In the worst case, we iterate from 1 up to `sqrt(num)`.
Space
O(1), as we only use a constant amount of extra space for the loop variable.
Trade-offs
Pros
Simple to understand and implement.
Requires minimal memory.
Cons
Inefficient for large input numbers.
May result in a 'Time Limit Exceeded' error on platforms with strict time limits.
A more efficient approach is to use binary search. Since the square roots of numbers are monotonically increasing, we can search for an integer x in the range [1, num] such that x * x = num.
Algorithm
- Initialize
left = 1andright = num. - Loop while
leftis less than or equal toright. - Calculate
mid = left + (right - left) / 2. Uselongto avoid overflow. - Calculate
square = mid * mid. - If
square == num, returntrue. - If
square < num, updateleft = mid + 1. - If
square > num, updateright = mid - 1. - If the loop ends, return
false.
Walkthrough
We are looking for an integer x where x * x = num. The possible values for x lie in a sorted range from 1 to num. This makes binary search an ideal candidate for finding x efficiently.
We define a search space with left = 1 and right = num.
We then repeatedly check the middle element mid of the current search space:
- We calculate
square = mid * mid. To avoid potential integer overflow,midandsquareshould be of typelong. - If
squareis equal tonum, we've found the integer square root, and we returntrue. - If
squareis less thannum, it means the actual square root must be larger thanmid. So, we discard the left half of the search space by settingleft = mid + 1. - If
squareis greater thannum, the square root must be smaller thanmid. We discard the right half by settingright = mid - 1.
This process continues until left becomes greater than right. If the loop terminates without finding a perfect square, we return false.
class Solution { public boolean isPerfectSquare(int num) { if (num < 1) return false; if (num == 1) return true; long left = 1; long right = num; while (left <= right) { long mid = left + (right - left) / 2; long square = mid * mid; if (square == num) { return true; } else if (square < num) { left = mid + 1; } else { right = mid - 1; } } return false; }}Complexity
Time
O(log n), where n is the input number `num`. The search space is halved in each iteration.
Space
O(1), as we only use a few variables to keep track of the search range.
Trade-offs
Pros
Significantly faster than linear search for large numbers.
Guaranteed to find the solution without hitting time limits.
Cons
Slightly more complex to conceptualize and implement than the brute-force approach.
Newton's method is a fast numerical technique for finding the root of a function. We can use it to find the square root of num by finding the root of the function f(x) = x^2 - num.
Algorithm
- Initialize a
longvariablexwith the value ofnumas an initial guess. - Loop as long as
x * xis greater thannum. - Inside the loop, update
xusing the formula:x = (x + num / x) / 2. - After the loop terminates,
xholds the integer floor of the square root ofnum. - Return
trueifx * x == num, andfalseotherwise.
Walkthrough
Newton's method is an iterative algorithm that produces successively better approximations of the roots of a function. To find sqrt(num), we seek the root of f(x) = x^2 - num.
The iteration formula is x_{k+1} = x_k - f(x_k) / f'(x_k). For our function, this simplifies to x_{k+1} = (x_k + num / x_k) / 2.
We can start with an initial guess, for instance, x = num. We then repeatedly apply the update rule. The sequence of x values converges very quickly to the actual square root of num.
The loop continues as long as our guess x squared is greater than num. Once the loop terminates, x will be the integer part of the square root.
Finally, we check if x * x is exactly equal to num to confirm if it's a perfect square.
class Solution { public boolean isPerfectSquare(int num) { if (num < 1) return false; long x = num; while (x * x > num) { x = (x + num / x) / 2; } return x * x == num; }}Complexity
Time
O(log n). The convergence is quadratic, meaning the number of correct digits roughly doubles with each iteration. It's generally faster than binary search.
Space
O(1), as it only requires a single variable for the iteration.
Trade-offs
Pros
Extremely fast convergence.
Elegant mathematical solution.
Cons
The underlying mathematical concept might be less familiar than binary search.
Requires careful handling of integer division and potential edge cases.
Solutions
Solution
class Solution { public boolean isPerfectSquare ( int num ) { long left = 1 , right = num ; while ( left < right ) { long mid = ( left + right ) >>> 1 ; if ( mid * mid >= num ) { right = mid ; } else { left = mid + 1 ; } } return left * left == num ; } }class Solution { public: bool isPerfectSquare ( int num ) { long left = 1 , right = num ; while ( left < right ) { long mid = left + right >> 1 ; if ( mid * mid >= num ) right = mid ; else left = mid + 1 ; } return left * left == num ; } };class Solution : def isPerfectSquare ( self , num : int ) -> bool : left , right = 1 , num while left < right : mid = ( left + right ) >> 1 if mid * mid >= num : right = mid else : left = mid + 1 return left * left == numVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.