Sqrt(x)

EASY

Description

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

Approaches

Checkout 3 different approaches to solve Sqrt(x). Click on different approaches to view the approach and algorithm in detail.

Brute Force using Linear Search

This approach involves iterating through numbers starting from 1 and checking if their square is equal to or just exceeds the input x. The integer square root is the largest integer i for which i*i <= x.

Algorithm

Handle the edge case where x is 0. If x is 0, the square root is 0.
Initialize a loop counter i to 1. Use a long for i to prevent overflow during multiplication.
In each iteration, check if i * i > x.
If this condition is met, it means (i-1)*(i-1) <= x and i*i > x. Therefore, i-1 is the answer. Return (int)(i-1).
If i * i == x, then i is the perfect square root, return (int)i.
The loop will eventually terminate because for a large enough i, i*i will exceed x.

We can iterate with a variable i from 1 upwards. For each i, we compute its square. To avoid integer overflow when calculating i*i for large i, it's crucial to use a larger data type, like long in Java. The loop continues as long as i*i <= x. When the loop finds an i such that i*i > x, the previous integer, i-1, must be the integer square root of x.

class Solution {
    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        for (long i = 1; i <= x; i++) {
            if (i * i > x) {
                return (int) (i - 1);
            }
            if (i * i == x) {
                return (int) i;
            }
        }
        return -1; // Should not be reached for non-negative x
    }
}

Complexity Analysis

Time Complexity: O(sqrt(x))Space Complexity: O(1)

Pros and Cons

Pros:

Simple to understand and implement.

Cons:

Inefficient for large values of x. It can lead to a "Time Limit Exceeded" error on online judges.

Code Solutions

Checking out 5 solutions in different languages for Sqrt(x). Click on different languages to view the code.

public class Solution { public int MySqrt ( int x ) { int l = 0 , r = x ; while ( l < r ) { int mid = ( l + r + 1 ) >>> 1 ; if ( mid > x / mid ) { r = mid - 1 ; } else { l = mid ; } } return l ; } }

Video Solution

Watch the video walkthrough for Sqrt(x)

Algorithms:

Binary Search

Patterns:

Math

Companies:

Accenture |Adobe |Amazon |Apple |