Jobs

Interviews

Discussions

Sqrt(x)

Easy

Apple

1 view

Topics:

Binary Search

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.

You must not use any built-in exponent function or operator.

For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.

Example 1:

Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.

Example 2:

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.

Constraints:

0 <= x <= 2^31 - 1

Can you implement a function to solve this problem in Python?

Sqrt(x)

Easy

Apple

1 view

Topics:

Binary Search

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.

You must not use any built-in exponent function or operator.

For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.

Example 1:

Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.

Example 2:

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.

Constraints:

0 <= x <= 2^31 - 1

Can you implement a function to solve this problem in Python?

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 maximum possible value of the input x?
If x is 0, should I return 0?
Since the return type is an integer and we are truncating the decimal part, what should I return if x is a very large number whose square root is non-integer, e.g., x = 99?
Is the input guaranteed to be a non-negative integer, or do I need to validate the input?
Are there any specific error conditions I need to handle, such as non-integer or negative input (even though the problem states non-negative, confirming this shows thoroughness)?

Brute Force Solution

Approach

The brute force method to find the square root of a number involves systematically checking possible answers. We essentially guess and check every whole number, starting from the smallest possible value, until we find one that, when squared, equals or gets very close to the given number. If the square of our guess exceeds the number, we know our previous guess was the closest integer square root.

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

Start with the smallest whole number, zero.
Calculate the square of this number.
Compare the square with the given number. If the square is equal to the given number, we found the square root!
If the square is larger than the given number, the previous number was the square root.
If the square is smaller than the given number, try the next whole number and repeat the process.

Code Implementation

def my_sqrt(number_to_square_root):
    possible_square_root = 0

    while True:
        square_of_possible_root = possible_square_root * possible_square_root

        # If perfect match, return the root
        if square_of_possible_root == number_to_square_root:
            return possible_square_root

        # If square is too big, the previous number was the closest root.
        if square_of_possible_root > number_to_square_root:

            return possible_square_root - 1

        # We haven't found it yet, so increment and continue
        possible_square_root += 1

Big(O) Analysis

Time Complexity

O(sqrt(x)) – The brute force method iterates through numbers starting from 0, incrementing by 1, until the square of the current number exceeds the input number x. In the worst-case scenario, the algorithm iterates up to the square root of x. Therefore, the number of iterations is directly proportional to the square root of x, making the time complexity O(sqrt(x)).

Space Complexity

O(1) – The algorithm described in the plain English explanation uses only a few constant space variables. These variables include the current guess for the square root and the square of that guess. Since the space required does not grow with the input number x, the space complexity is constant.

Optimal Solution

Approach

The most efficient way to find the square root of a number is to use a guessing game that gets smarter over time. Instead of checking every single number one by one, we make an initial guess and then repeatedly refine it to get closer and closer to the true square root.

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

Start by making a wide guess about what the square root might be. A good starting guess would be half of the number.
Square your guess. If it's too big, you know the real square root must be smaller, and if it's too small, the real square root must be bigger.
Based on whether your guess was too big or too small, adjust your guess to be closer to the real square root. Cut the search range into half and decide which half to continue on.
Repeat the process of squaring your adjusted guess and refining it until you get very close to the true square root. Each time you repeat, your guess becomes more and more accurate.
Once the difference between your squared guess and the original number is small enough, you can stop and return your latest guess as the approximate square root.

Code Implementation

def my_sqrt(x):
    if x == 0:
        return 0

    initial_guess = x / 2.0
    tolerance = 0.00001

    while True:
        squared_guess = initial_guess * initial_guess

        # Check if our guess is close enough to the actual square root
        if abs(squared_guess - x) < tolerance:
            return int(initial_guess)

        # If the guess is too high, adjust it to be lower
        if squared_guess > x:

            initial_guess = (initial_guess + (x / initial_guess)) / 2
            
        else:
            # If the guess is too low, adjust it to be higher
            initial_guess = (initial_guess + (x / initial_guess)) / 2

        #Updating according to Newton's method to reduce iterations

Big(O) Analysis

Time Complexity

O(log n) – The algorithm uses a binary search approach to find the square root. The input size is represented by the number x. In each iteration, the search space is halved, effectively reducing the problem size by a factor of 2. The number of iterations required to converge to the square root is therefore logarithmic with respect to x. Thus, the time complexity is O(log x), which we can denote as O(log n) where n represents the input number.

Space Complexity

O(1) – The algorithm primarily utilizes a few variables to store the current guess and potentially the low and high bounds for the search space. The number of these variables does not depend on the input number 'x'. Therefore, the space used remains constant regardless of the input size, resulting in a space complexity of O(1).

Edge Cases

Case	How to Handle
x = 0	Return 0 since the square root of 0 is 0.
x = 1	Return 1 since the square root of 1 is 1.
x is a large perfect square that causes integer overflow if its true square root is calculated without precautions.	Use long integer arithmetic during binary search or other root-finding methods to prevent overflow when squaring mid values.
x is very large (close to MAX_INT)	Handle this case correctly using binary search, as linear iteration would be inefficient.
x = Integer.MAX_VALUE	Binary search should be implemented carefully to prevent overflow when calculating mid * mid.
x is a perfect square, but very large	Binary search should quickly converge to the correct integer square root.
x is a non-perfect square	The algorithm should correctly truncate the decimal part and return the integer part of the square root.
Negative input for x	The problem description specifies non-negative integers, but handling negative input by either throwing an exception or returning 0 for invalid input enhances robustness.

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 maximum possible value of the input x?
If x is 0, should I return 0?
Since the return type is an integer and we are truncating the decimal part, what should I return if x is a very large number whose square root is non-integer, e.g., x = 99?
Is the input guaranteed to be a non-negative integer, or do I need to validate the input?
Are there any specific error conditions I need to handle, such as non-integer or negative input (even though the problem states non-negative, confirming this shows thoroughness)?

Brute Force Solution

Approach

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

Start with the smallest whole number, zero.
Calculate the square of this number.
Compare the square with the given number. If the square is equal to the given number, we found the square root!
If the square is larger than the given number, the previous number was the square root.
If the square is smaller than the given number, try the next whole number and repeat the process.

Code Implementation

def my_sqrt(number_to_square_root):
    possible_square_root = 0

    while True:
        square_of_possible_root = possible_square_root * possible_square_root

        # If perfect match, return the root
        if square_of_possible_root == number_to_square_root:
            return possible_square_root

        # If square is too big, the previous number was the closest root.
        if square_of_possible_root > number_to_square_root:

            return possible_square_root - 1

        # We haven't found it yet, so increment and continue
        possible_square_root += 1

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start by making a wide guess about what the square root might be. A good starting guess would be half of the number.
Square your guess. If it's too big, you know the real square root must be smaller, and if it's too small, the real square root must be bigger.
Based on whether your guess was too big or too small, adjust your guess to be closer to the real square root. Cut the search range into half and decide which half to continue on.
Repeat the process of squaring your adjusted guess and refining it until you get very close to the true square root. Each time you repeat, your guess becomes more and more accurate.
Once the difference between your squared guess and the original number is small enough, you can stop and return your latest guess as the approximate square root.

Code Implementation

def my_sqrt(x):
    if x == 0:
        return 0

    initial_guess = x / 2.0
    tolerance = 0.00001

    while True:
        squared_guess = initial_guess * initial_guess

        # Check if our guess is close enough to the actual square root
        if abs(squared_guess - x) < tolerance:
            return int(initial_guess)

        # If the guess is too high, adjust it to be lower
        if squared_guess > x:

            initial_guess = (initial_guess + (x / initial_guess)) / 2
            
        else:
            # If the guess is too low, adjust it to be higher
            initial_guess = (initial_guess + (x / initial_guess)) / 2

        #Updating according to Newton's method to reduce iterations

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
x = 0	Return 0 since the square root of 0 is 0.
x = 1	Return 1 since the square root of 1 is 1.
x is a large perfect square that causes integer overflow if its true square root is calculated without precautions.	Use long integer arithmetic during binary search or other root-finding methods to prevent overflow when squaring mid values.
x is very large (close to MAX_INT)	Handle this case correctly using binary search, as linear iteration would be inefficient.
x = Integer.MAX_VALUE	Binary search should be implemented carefully to prevent overflow when calculating mid * mid.
x is a perfect square, but very large	Binary search should quickly converge to the correct integer square root.
x is a non-perfect square	The algorithm should correctly truncate the decimal part and return the integer part of the square root.
Negative input for x	The problem description specifies non-negative integers, but handling negative input by either throwing an exception or returning 0 for invalid input enhances robustness.