Jobs

Interviews

Discussions

Valid Perfect Square

#1324 Most AskedEasy

Valid Perfect Square #1324 Most Asked

Easy

Google

7 views

Topics:

Binary Search

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 <= 2³¹ - 1

Try coding it in LeetCode

Valid Perfect Square

#1324 Most AskedEasy

Valid Perfect Square #1324 Most Asked

Easy

Google

7 views

Topics:

Binary Search

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 <= 2³¹ - 1

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the upper bound for the input integer `num`? This will help me decide on the appropriate algorithm to use.
Is `num` guaranteed to be a positive integer, or should I handle cases where `num` is zero or negative?
Can you provide examples of edge cases, such as very small or very large perfect squares, to ensure my solution handles them correctly?
What is the expected return type if the input is not a perfect square (e.g., boolean, null, exception)?
Are there any specific error handling requirements, such as throwing an exception if the input is invalid?

Brute Force Solution

Approach

The problem asks us to determine if a given number is a perfect square. The brute force approach involves checking every possible whole number to see if its square equals the given number.

Here's how the algorithm would work step-by-step:

Start with the number one.
Calculate the square of that number.
See if the square is equal to the given number. If it is, you've found the perfect square and the answer is yes.
If the square is larger than the given number, then you know there are no more perfect squares to be found and the answer is no.
If the square is smaller than the given number, increase the original number by one and repeat the process from step two.
Continue this process until you either find the perfect square or determine it doesn't exist.

Code Implementation

def is_valid_perfect_square_brute_force(number):
    current_number = 1

    while True:
        square = current_number * current_number

        # If the square equals the number, it's a perfect square
        if square == number:
            return True

        # If the square is larger, the number isn't a perfect square
        if square > number:
            return False

        # Increment the current number to check the next square
        current_number += 1

Big(O) Analysis

Time Complexity

O(sqrt(n)) – The given solution iterates starting from 1, calculating the square of each number until the square is either equal to or exceeds the input number n. In the worst case, the loop iterates up to the square root of n (sqrt(n)). Therefore, the number of iterations is proportional to sqrt(n), resulting in a time complexity of O(sqrt(n)).

Space Complexity

O(1) – The described algorithm uses a single variable to represent the number being squared and another implicit variable to store the square itself during the calculation within the loop. Regardless of the input number N, the algorithm does not allocate any additional data structures like arrays or hash maps. Therefore, the space complexity is constant, independent of the input size.

Optimal Solution

Approach

Instead of checking every possible number, we can use a more efficient search strategy. This strategy eliminates large portions of potential numbers quickly, focusing only on the most promising candidates. By doing this, we avoid unnecessary calculations and find the answer much faster.

Here's how the algorithm would work step-by-step:

Start by considering a range of possible numbers that could be the square root of the input.
Take the middle number within that range and square it.
Compare the result to the input number. If the squared value is equal to the input, then you've found the square root, and therefore the input is a perfect square.
If the squared value is too big, narrow your range to only consider numbers smaller than your current middle number.
If the squared value is too small, narrow your range to only consider numbers larger than your current middle number.
Repeat steps 2 through 5 until you find the square root or the range becomes empty. If the range becomes empty, the original number is not a perfect square.

Code Implementation

def is_perfect_square(number):
    if number < 0:
        return False

    low_range = 0
    high_range = number

    while low_range <= high_range:
        mid_range = (low_range + high_range) // 2
        squared_value = mid_range * mid_range

        if squared_value == number:
            return True

        elif squared_value < number:
            # The square root must be larger, so adjust the lower bound.
            low_range = mid_range + 1

        else:
            # The square root must be smaller, so adjust the upper bound.
            high_range = mid_range - 1

    # If the loop finishes without finding a square root,
    # the number is not a perfect square.
    return False

Big(O) Analysis

Time Complexity

O(log n) – The algorithm uses binary search to find the square root of the input number n. In each iteration, the search space is halved. The number of iterations required to find the square root or determine that it doesn't exist is logarithmic with respect to n. Therefore, the time complexity is O(log n).

Space Complexity

O(1) – The algorithm described uses a binary search approach to find the perfect square. It operates by maintaining a range and repeatedly calculating the middle element's square. This involves only a few constant extra variables to store the low and high bounds of the search range and the middle element. Therefore, no auxiliary data structures that scale with the input number (N) are used, resulting in constant space complexity.

Edge Cases

Case	How to Handle
Input is 0	Return true since 0 * 0 = 0 and 0 is a perfect square.
Input is 1	Return true since 1 * 1 = 1 and 1 is a perfect square.
Input is a large perfect square close to the maximum integer value (Integer.MAX_VALUE)	Use long for calculations to prevent potential integer overflow during the square root calculation or squaring the mid value.
Input is a number slightly larger than a perfect square	The binary search should correctly narrow down the search space and return false.
Input is a negative number	Return false, as perfect squares are non-negative.
Input is Integer.MAX_VALUE	Utilize long to prevent overflow, calculate the square root or use binary search until the middle element surpasses the boundary
Input is a perfect square represented by the maximum value of a smaller data type (e.g., Short.MAX_VALUE)	The algorithm should handle the input as a perfect square without any data type limitation issues if we are using Integer or Long.
Algorithm using Math.sqrt() might have floating-point precision issues.	Compare the square of the integer part of the square root against the input to avoid floating-point inaccuracies.

Input is 0

How to Handle:

Return true since 0 * 0 = 0 and 0 is a perfect square.

Input is 1

How to Handle:

Return true since 1 * 1 = 1 and 1 is a perfect square.

Input is a large perfect square close to the maximum integer value (Integer.MAX_VALUE)

How to Handle:

Use long for calculations to prevent potential integer overflow during the square root calculation or squaring the mid value.

Input is a number slightly larger than a perfect square

How to Handle:

The binary search should correctly narrow down the search space and return false.

Input is a negative number

How to Handle:

Return false, as perfect squares are non-negative.

Input is Integer.MAX_VALUE

How to Handle:

Utilize long to prevent overflow, calculate the square root or use binary search until the middle element surpasses the boundary

Input is a perfect square represented by the maximum value of a smaller data type (e.g., Short.MAX_VALUE)

How to Handle:

The algorithm should handle the input as a perfect square without any data type limitation issues if we are using Integer or Long.

Algorithm using Math.sqrt() might have floating-point precision issues.

How to Handle:

Compare the square of the integer part of the square root against the input to avoid floating-point inaccuracies.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the upper bound for the input integer `num`? This will help me decide on the appropriate algorithm to use.
Is `num` guaranteed to be a positive integer, or should I handle cases where `num` is zero or negative?
Can you provide examples of edge cases, such as very small or very large perfect squares, to ensure my solution handles them correctly?
What is the expected return type if the input is not a perfect square (e.g., boolean, null, exception)?
Are there any specific error handling requirements, such as throwing an exception if the input is invalid?

Brute Force Solution

Approach

The problem asks us to determine if a given number is a perfect square. The brute force approach involves checking every possible whole number to see if its square equals the given number.

Here's how the algorithm would work step-by-step:

Start with the number one.
Calculate the square of that number.
See if the square is equal to the given number. If it is, you've found the perfect square and the answer is yes.
If the square is larger than the given number, then you know there are no more perfect squares to be found and the answer is no.
If the square is smaller than the given number, increase the original number by one and repeat the process from step two.
Continue this process until you either find the perfect square or determine it doesn't exist.

Code Implementation

def is_valid_perfect_square_brute_force(number):
    current_number = 1

    while True:
        square = current_number * current_number

        # If the square equals the number, it's a perfect square
        if square == number:
            return True

        # If the square is larger, the number isn't a perfect square
        if square > number:
            return False

        # Increment the current number to check the next square
        current_number += 1

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start by considering a range of possible numbers that could be the square root of the input.
Take the middle number within that range and square it.
Compare the result to the input number. If the squared value is equal to the input, then you've found the square root, and therefore the input is a perfect square.
If the squared value is too big, narrow your range to only consider numbers smaller than your current middle number.
If the squared value is too small, narrow your range to only consider numbers larger than your current middle number.
Repeat steps 2 through 5 until you find the square root or the range becomes empty. If the range becomes empty, the original number is not a perfect square.

Code Implementation

def is_perfect_square(number):
    if number < 0:
        return False

    low_range = 0
    high_range = number

    while low_range <= high_range:
        mid_range = (low_range + high_range) // 2
        squared_value = mid_range * mid_range

        if squared_value == number:
            return True

        elif squared_value < number:
            # The square root must be larger, so adjust the lower bound.
            low_range = mid_range + 1

        else:
            # The square root must be smaller, so adjust the upper bound.
            high_range = mid_range - 1

    # If the loop finishes without finding a square root,
    # the number is not a perfect square.
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input is 0	Return true since 0 * 0 = 0 and 0 is a perfect square.
Input is 1	Return true since 1 * 1 = 1 and 1 is a perfect square.
Input is a large perfect square close to the maximum integer value (Integer.MAX_VALUE)	Use long for calculations to prevent potential integer overflow during the square root calculation or squaring the mid value.
Input is a number slightly larger than a perfect square	The binary search should correctly narrow down the search space and return false.
Input is a negative number	Return false, as perfect squares are non-negative.
Input is Integer.MAX_VALUE	Utilize long to prevent overflow, calculate the square root or use binary search until the middle element surpasses the boundary
Input is a perfect square represented by the maximum value of a smaller data type (e.g., Short.MAX_VALUE)	The algorithm should handle the input as a perfect square without any data type limitation issues if we are using Integer or Long.
Algorithm using Math.sqrt() might have floating-point precision issues.	Compare the square of the integer part of the square root against the input to avoid floating-point inaccuracies.

Input is 0

How to Handle:

Return true since 0 * 0 = 0 and 0 is a perfect square.

Input is 1

How to Handle:

Return true since 1 * 1 = 1 and 1 is a perfect square.

Input is a large perfect square close to the maximum integer value (Integer.MAX_VALUE)

How to Handle:

Use long for calculations to prevent potential integer overflow during the square root calculation or squaring the mid value.

Input is a number slightly larger than a perfect square

How to Handle:

The binary search should correctly narrow down the search space and return false.

Input is a negative number

How to Handle:

Return false, as perfect squares are non-negative.

Input is Integer.MAX_VALUE

How to Handle:

Utilize long to prevent overflow, calculate the square root or use binary search until the middle element surpasses the boundary

Input is a perfect square represented by the maximum value of a smaller data type (e.g., Short.MAX_VALUE)

How to Handle:

The algorithm should handle the input as a perfect square without any data type limitation issues if we are using Integer or Long.

Algorithm using Math.sqrt() might have floating-point precision issues.

How to Handle:

Compare the square of the integer part of the square root against the input to avoid floating-point inaccuracies.

0/1916 Google questions completed

0/1916 completed