Grokking the Coding Interview: Patterns for Coding Questions

0% completed

Sqrt (medium)

On This Page

Problem Statement

Try it yourself

Problem Statement

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 = 8
Output: 2
Explanation: The square root of 8 is 2.8284, and since we need to return the floor of the square root (integer), hence we returned 2.

Example 2:

Input: x = 4
Output: 2
Explanation: The square root of 4 is 2.

Example 3:

Input: x = 2
Output: 1
Explanation: The square root of 2 is 1.414, and since we need to return the floor of the square root (integer), hence we returned 1.

Constraints:

0 <= x <= 2<sup>31</sup> - 1

Try it yourself

Try solving this question here:

Python3

. . . .

For a detailed solution, see the next chapter.

Mark as Completed

Anonymous

· 3 years ago

I just wanted to suggest a more subtle way of explaining it that may be a bit better. So, binary search is applied here because we are searching for a value in a specific range of values, which is a range of sorted numbers. That value we are looking for is the largest value n such that n * n <= x. So, we can use a variable to store the result, and if we ever find a value whose square is <= x, update the result to that. However, since our goal is to find the largest, toss that pivot out and set left = mid + 1. If the square is too large, then we want to lower our right bound and set right = mid - 1.

class Solution {
  public int mySqrt(int x) {
    int left = 0;
    int right = x;
    int res = 0;

    while(left <= right){
      int mid = left + (right - left) / 2;

      if((long

Roberto Pantoja

· 3 years ago

I came up with the following solution.

class Solution {
public:
  int mySqrt(int x) {
    int i = 0;

    while(i * i <= x){i++;}

    // TODO: Write your code here
    return i - 1;
  }
};

Basically, just increment i until you pass the square root, then return previous value.

Am I missing something? Why is the more complex solution the example?

Show 8 replies

Vishnu S Nair

· a year ago

Show 1 reply

Jlsegb

· 6 months ago

You can ask an LLM to explain it. But this is a neat way of calculating a root. Probably better to use the binary tree solution but this one performs better O(log log n)

class Solution {
public:
    int mySqrt(int x) {
        if (x == 0) return 0;

        int r = x;
        while (r > x / r) {   // instead of r*r > x
            r = (r + x / r) / 2; // this is Newton's method.
        }
        return (int)r; // floor(sqrt(x))
    }
};

Note that we should avoid a possible integer overflow from r*r by re-arranging the equality or using a bigger container.

Manuel

· 2 years ago

Show 1 reply

vladyslav.chikov

· 8 months ago

There is a solution which in terms of big-O notation is not that good as binary search, but good enough for the most of modern numbers.

The first instinct you want to go is:

class Solution:
  def mySqrt(self, x: int) -> int:
    i = 0
    step = 1
    while (i+1) * (i+1) <= x:
      i += 1
    return i

This algo is O(X^{1/2}) which is not bad and will work on any modern CPU all the way till 10^14-10^16

But you quickly realise that if your input is, say, 10**16, and you do i = 1, then likely do i=2,3,4,5 is pretty useless.

Instead we can do an incremental jump size too to increase the growth. Once we cross the bar, we slow down the growth until it stops:

class Solution:
  def mySqrt(self, x: int) -> int:
    i = 0
    step = 1
    while (i+step) * (i+step) <=

On This Page

Problem Statement

Try it yourself