Jobs

Interviews

Discussions

Valid Perfect Square

Easy

Amazon

2 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

Valid Perfect Square

Easy

Amazon

2 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

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:

Is the input guaranteed to be a non-negative integer?
If the input is not a perfect square, what value should I return? For example, should I return false, -1, or throw an exception?
What is the maximum possible value of the input number?
Should I be concerned about integer overflow during the calculation, and if so, how should I handle it?
Are there any memory constraints I should be aware of?

Brute Force Solution

Approach

To check if a number is a perfect square using the brute force strategy, we can try multiplying numbers by themselves. We'll start with a small number and keep increasing it, checking if the square of that number matches the given number.

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

Start with the number one.
Multiply the current number by itself.
Check if the result of the multiplication is equal to the given number.
If it is, then the given number is a perfect square.
If it is not, then increase the current number by one.
Repeat steps two through five until the result of the multiplication is greater than the given number.
If we reach a point where the square is greater than the number, and we never found an exact match, then the number is not a perfect square.

Code Implementation

def is_valid_perfect_square(number) -> bool:
    current_number = 1

    while True:
        square = current_number * current_number

        # If the square is equal to the number, we found a perfect square
        if square == number:
            return True

        #If the square is greater than the number, it can't be a perfect square
        if square > number:
            return False

        #Increment and try the next number

        current_number += 1

Big(O) Analysis

Time Complexity

O(sqrt(n)) – The input is a single number 'n'. The algorithm iterates, starting from 1, and squares each number in the loop. The loop continues until the square exceeds 'n'. This means the loop variable will roughly reach the square root of 'n' before terminating. Therefore, the time complexity is proportional to the square root of the input number n, resulting in O(sqrt(n)).

Space Complexity

O(1) – The provided algorithm uses a single variable to track the current number being squared. This variable, along with the input number itself, are the only memory requirements. The amount of memory used does not scale with the input number N; it remains constant. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

Instead of checking every number, the best way to find out if a number is a perfect square is to use a guessing game that quickly narrows down the possibilities. It's like playing 'higher or lower' to find the square root without calculating every square.

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

Start with a reasonable guess for the square root (like half of the number).
Square your guess and see if it matches the original number.
If your guess squared is too big, make your guess smaller.
If your guess squared is too small, make your guess bigger.
Keep adjusting your guess until you either find the square root, or your 'bigger' guess becomes smaller than your 'smaller' guess. If that happens, the original number isn't a perfect square.

Code Implementation

def is_perfect_square(number) -> bool:
    if number < 0:
        return False
    
    low_range = 0
    high_range = number

    while low_range <= high_range:
        potential_root = (low_range + high_range) // 2
        square_of_potential_root = potential_root * potential_root

        if square_of_potential_root == number:
            return True

        elif square_of_potential_root < number:
            # Guess was too low, increase lower bound.
            low_range = potential_root + 1

        else:
            # Guess was too high, decrease higher bound.
            high_range = potential_root - 1

    #If low > high, then the number is not a perfect square
    return False

Big(O) Analysis

Time Complexity

O(log n) – The algorithm uses a binary search approach to find the square root. 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 proportional to the logarithm base 2 of the input number n. Therefore, the time complexity is O(log n).

Space Complexity

O(1) – The algorithm uses a constant amount of extra space. It only requires a few variables to store the current guess, a lower bound, and an upper bound, regardless of the input number N. These variables occupy a fixed amount of memory, independent of the size of N. Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
Input is zero	Return true since 0 * 0 = 0
Input is a negative number	Return false as perfect squares are non-negative
Input is 1	Return true since 1 * 1 = 1
Input is the maximum possible integer	The chosen algorithm (binary search) should handle this case gracefully by adjusting the range accordingly, but integer overflow could be a concern in other approaches requiring multiplication.
Square root exceeds the maximum integer representable in the language (potential overflow)	Use long or a larger data type to perform the square calculation to prevent overflow, or use division to check.
Input is a large perfect square (e.g., close to the maximum integer)	Binary search should converge correctly and efficiently find the integer square root without significant performance issues.
Input is a number that is close to a perfect square but isn't one	Binary search needs to check precisely after convergence whether square of mid equals the input.
Very large input numbers that require a large range for the binary search.	Binary search implementation handles this automatically by dynamically adjusting search space ensuring logarithmic time complexity.

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:

Is the input guaranteed to be a non-negative integer?
If the input is not a perfect square, what value should I return? For example, should I return false, -1, or throw an exception?
What is the maximum possible value of the input number?
Should I be concerned about integer overflow during the calculation, and if so, how should I handle it?
Are there any memory constraints I should be aware of?

Brute Force Solution

Approach

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

Start with the number one.
Multiply the current number by itself.
Check if the result of the multiplication is equal to the given number.
If it is, then the given number is a perfect square.
If it is not, then increase the current number by one.
Repeat steps two through five until the result of the multiplication is greater than the given number.
If we reach a point where the square is greater than the number, and we never found an exact match, then the number is not a perfect square.

Code Implementation

def is_valid_perfect_square(number) -> bool:
    current_number = 1

    while True:
        square = current_number * current_number

        # If the square is equal to the number, we found a perfect square
        if square == number:
            return True

        #If the square is greater than the number, it can't be a perfect square
        if square > number:
            return False

        #Increment and try the next number

        current_number += 1

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start with a reasonable guess for the square root (like half of the number).
Square your guess and see if it matches the original number.
If your guess squared is too big, make your guess smaller.
If your guess squared is too small, make your guess bigger.
Keep adjusting your guess until you either find the square root, or your 'bigger' guess becomes smaller than your 'smaller' guess. If that happens, the original number isn't a perfect square.

Code Implementation

def is_perfect_square(number) -> bool:
    if number < 0:
        return False
    
    low_range = 0
    high_range = number

    while low_range <= high_range:
        potential_root = (low_range + high_range) // 2
        square_of_potential_root = potential_root * potential_root

        if square_of_potential_root == number:
            return True

        elif square_of_potential_root < number:
            # Guess was too low, increase lower bound.
            low_range = potential_root + 1

        else:
            # Guess was too high, decrease higher bound.
            high_range = potential_root - 1

    #If low > high, then the number is not a perfect square
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input is zero	Return true since 0 * 0 = 0
Input is a negative number	Return false as perfect squares are non-negative
Input is 1	Return true since 1 * 1 = 1
Input is the maximum possible integer	The chosen algorithm (binary search) should handle this case gracefully by adjusting the range accordingly, but integer overflow could be a concern in other approaches requiring multiplication.
Square root exceeds the maximum integer representable in the language (potential overflow)	Use long or a larger data type to perform the square calculation to prevent overflow, or use division to check.
Input is a large perfect square (e.g., close to the maximum integer)	Binary search should converge correctly and efficiently find the integer square root without significant performance issues.
Input is a number that is close to a perfect square but isn't one	Binary search needs to check precisely after convergence whether square of mid equals the input.
Very large input numbers that require a large range for the binary search.	Binary search implementation handles this automatically by dynamically adjusting search space ensuring logarithmic time complexity.