69. Sqrt(x)

leetcode easy

#csharp#easy#leetcode#math#two-pointers

Task

Дано неотрицательное целое число x. Верните квадратный корень из x, округлённый вниз до ближайшего целого числа. Возвращаемое целое число также должно быть неотрицательным.

Вы не должны использовать встроенные функции или операторы для возведения в степень.

Например, не следует использовать pow(x, 0.5) в C++ или x ** 0.5 в Python.

Пример:

Input: x = 4

Output: 2

Explanation: The square root of 4 is 2, so we return 2.

C# solution

matched/original

public class Solution {
    public int MySqrt(int x) {
        if (x < 2)
            return x;
        long num;
        int pivot, left = 2, right = x / 2;
        while (left <= right) {
            pivot = left + (right - left) / 2;
            num = (long)pivot * pivot;
            if (num > x)
                right = pivot - 1;
            else if (num < x)
                left = pivot + 1;
            else
                return pivot;
        }
        return right;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MySqrt(int x) {
        if (x < 2)
            return x;
        long num;
        int pivot, left = 2, right = x / 2;
        while (left <= right) {
            pivot = left + (right - left) / 2;
            num = (long)pivot * pivot;
            if (num > x)
                right = pivot - 1;
            else if (num < x)
                left = pivot + 1;
            else
                return pivot;
        }
        return right;
    }
}

Java solution

matched/original

class Solution {
    public int mySqrt(int x) {
        if (x < 2) return x;

        long num;
        int pivot, left = 2, right = x / 2;
        while (left <= right) {
            pivot = left + (right - left) / 2;
            num = (long) pivot * pivot;
            if (num > x) right = pivot - 1;
            else if (num < x) left = pivot + 1;
            else return pivot;
        }

        return right;
    }
}

JavaScript solution

matched/original

var mySqrt = function (x) {
    if (x < 2) return x;
    let num;
    let pivot,
        left = 2,
        right = Math.floor(x / 2);
    while (left <= right) {
        pivot = left + Math.floor((right - left) / 2);
        num = pivot * pivot;
        if (num > x) right = pivot - 1;
        else if (num < x) left = pivot + 1;
        else return pivot;
    }
    return right;
};

Python solution

matched/original

class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x

        left, right = 2, x // 2

        while left <= right:
            pivot = left + (right - left) // 2
            num = pivot * pivot
            if num > x:
                right = pivot - 1
            elif num < x:
                left = pivot + 1
            else:
                return pivot

        return right

Go solution

matched/original

func mySqrt(x int) int {
    if x < 2 {
        return x
    }
    var num int
    pivot, left, right := 2, 2, x/2
    for left <= right {
        pivot = left + (right-left)/2
        num = pivot * pivot
        if num > x {
            right = pivot - 1
        } else if num < x {
            left = pivot + 1
        } else {
            return pivot
        }
    }
    return right
}

Explanation

Algorithm

1️⃣

Если x < 2, верните x. Установите левую границу left = 2 и правую границу right = x / 2.

2️⃣

Пока left ≤ right:

Возьмите num = (left + right) / 2 в качестве предположения. Вычислите num × num и сравните его с x:

Если num × num > x, переместите правую границу right = pivot − 1.

В противном случае, если num × num < x, переместите левую границу left = pivot + 1.

В противном случае num × num == x, целочисленный квадратный корень найден, давайте вернем его.

3️⃣

Верните right.

😎