367. Valid Perfect Square
Model: qwen2.5-coder:14b
Topics: Math,Binary Search
FAANG asked: 1
Acceptance rate: 42.2%
Problem Breakdown
The problem asks us to determine whether a given positive integer num is a perfect square. A perfect square is an integer that is the square of another integer. For example, 16 is a perfect square because it can be expressed as 4 * 4.
Inputs:
- A single positive integer
num(1 <= num <= 2^31 - 1).
Outputs:
- A boolean value:
Trueifnumis a perfect square, otherwiseFalse.
Implicit Constraints or Tricky Edge Cases:
- The input range is quite large (up to 2^31 - 1), so the solution must be efficient in terms of time and space.
- We cannot use any built-in library functions like
sqrt. - Consider edge cases such as the smallest number, 1, which is a perfect square.
Intuition
A brute-force approach would involve iterating from 1 to num and checking if the square of any number equals num. However, this approach has a time complexity of O(n), which is inefficient for large values of num.
The key insight is that we can use binary search to efficiently determine whether num is a perfect square. Binary search reduces the time complexity to O(log n) by repeatedly dividing the search interval in half.
Approach
- Initialize Pointers: Set two pointers,
leftandright, whereleftstarts at 1 andrightstarts atnum // 2. We startrightatnum // 2because any perfect square greater than 1 will have its square root less than or equal tonum // 2. - Binary Search Loop:
- Calculate the midpoint
midbetweenleftandright. - Compute
mid * mid. - If
mid * midequalsnum, thennumis a perfect square, returnTrue. - If
mid * midis less thannum, move theleftpointer tomid + 1. - If
mid * midis greater thannum, move therightpointer tomid - 1.
- Calculate the midpoint
- Termination: The loop terminates when
leftexceedsright. If no perfect square is found, returnFalse.
Complexity Analysis
- Time Complexity: O(log n) because we are using binary search.
- Space Complexity: O(1) as we are only using a constant amount of extra space for the pointers and variables.
Solution
def isPerfectSquare(num: int) -> bool:
if num < 2:
return True
left, right = 1, num // 2
while left <= right:
mid = (left + right) // 2
square = mid * mid
if square == num:
return True
elif square < num:
left = mid + 1
else:
right = mid - 1
return False
Edge Cases Handled
- Edge Case: Smallest Input (num = 1): The function correctly identifies that 1 is a perfect square.
- Edge Case: Largest Input (num = 2^31 - 1): The function efficiently handles the largest possible input within the given constraints.
- Edge Case: Non-perfect Square: The function correctly returns
Falsefor numbers like 14, which are not perfect squares.