Solution: Sqrt

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.

.....

Like the course? Get enrolled and start learning!

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

Show 1 reply

Anonymous

· 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 6 replies

Reading Progress

Vote for new content