algoadvance

Leetcode 367. Valid Perfect Square

Problem Statement

Determine if a given positive integer num is a perfect square. A perfect square is an integer that is the square of some integer. In other words, a perfect square is the product of some integer with itself.

For example, 1, 4, 9, and 16 are perfect squares while 3 and 10 are not.

Function Signature:

bool isPerfectSquare(int num);

Example:

Clarifying Questions

  1. What is the range of the input integer num?
    • The constraints are typically within the range of a 32-bit signed integer, i.e., 1 <= num <= 2^31 - 1.
  2. Can we use built-in functions like sqrt()?
    • For the sake of a comprehensive solution, it’s better not to use the built-in sqrt() function. Instead, we should demonstrate an algorithmic approach.
  3. Should we account for very large inputs?
    • Given C++ can handle squares up to 2^31 - 1, a solution should be efficient for large inputs within this range.

Strategy

The problem can be solved using several methods, but we’ll demonstrate a couple of efficient approaches:

Binary search can determine if num is a perfect square efficiently by checking the middle of the range from 1 to num.

Steps:

  1. Set left to 1 and right to num.
  2. While left is less than or equal to right:
    • Compute mid as the midpoint between left and right.
    • If mid * mid equals num, return true.
    • If mid * mid is less than num, move left to mid + 1.
    • If mid * mid is more than num, move right to mid - 1.
  3. If no perfect square is found, return false.

Time Complexity:

Approach 2: Newton’s Method

Newton’s Method (or Newton-Raphson method) can also be employed to iteratively approach the square root of num.

Steps:

  1. Start with an initial guess x equal to num.
  2. Iteratively update guess using the formula:
    • guess = (guess + num / guess) / 2
  3. Stop when guess * guess is close enough to num.

Time Complexity:

Here is the implementation using the Binary Search approach:

Code

bool isPerfectSquare(int num) {
    if (num < 1) return false; // Edge case handling

    long left = 1, right = num; // Use long to prevent potential overflow

    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;
}

Conclusion

This solution ensures that num is efficiently checked for being a perfect square using binary search. Given its logarithmic time complexity, it works well even for larger values within the range of a 32-bit signed integer.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI