69. Sqrt(x)

LeetCode easy original: C# #csharp #easy #leetcode #math #two-pointers

Task text is translated from Russian for the selected interface language. Code is left unchanged.

LeetCode Static

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

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

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

Example:

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
}

Algorithm

1️⃣

Если x < 2, return 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, integer квадратный корень найден, давайте вернем его.

3️⃣

return right.

😎

Vacancies for this task

Active vacancies with overlapping task tags are shown.

All vacancies

There are no active vacancies yet.