LeetCode 솔루션

[Easy - wk3 - Q1] 69. Sqrt(x)

Chloe 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.05.16 17:00

4,651 조회
4 댓글
0 추천
0 비추천
목록 게시글 쓰기

Given a non-negative integer x, compute and return the square root of x.

Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.

Note: You are not allowed to use any built-in exponent function or operator, such as pow(x, 0.5) or x ** 0.5.

Example 1:

Input: x = 4
Output: 2

Example 2:

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

Constraints:

0 <= x <= 231 - 1

#leetcode, #문제풀이, #easy, #linkedin, #amazon, #google, #apple, #adobe, #microsoft, #math, #binary search

링크

https://leetcode.com/problems/sqrtx/ 3888 회 연결

익명
작성일 2022.05.18 15:46

Python

Runtime: 52 ms, faster than 56.80% of Python3 online submissions for Sqrt(x).
Memory Usage: 13.8 MB, less than 57.29% of Python3 online submissions for Sqrt(x).

from math import e, log
class Solution:
    def mySqrt(self, x):
        if x < 2:
            return x
        
        left = int(e**(0.5 * log(x)))
        right = left + 1
        return left if right * right > x else right

Runtime: 51 ms, faster than 58.81% of Python3 online submissions for Sqrt(x).
Memory Usage: 13.8 MB, less than 57.29% of Python3 online submissions for Sqrt(x).

class Solution:
    def mySqrt(self, x):
        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

Python

Runtime: 52 ms, faster than 56.80% of Python3 online submissions for Sqrt(x).
Memory Usage: 13.8 MB, less than 57.29% of Python3 online submissions for Sqrt(x).

[code=python]from math import e, log
class Solution:
    def mySqrt(self, x):
        if x < 2:
            return x
        
        left = int(e**(0.5 * log(x)))
        right = left + 1
        return left if right * right > x else right[/code]

Runtime: 51 ms, faster than 58.81% of Python3 online submissions for Sqrt(x).
Memory Usage: 13.8 MB, less than 57.29% of Python3 online submissions for Sqrt(x).

[code=python]class Solution:
    def mySqrt(self, x):
        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[/code]

익명
작성일 2022.05.24 10:16

class Solution {
public:
    int mySqrt(int x) {
        return sqrt(x);
    }
};

ㅋㅋㅋㅋㅋ

익명
작성일 2022.05.24 10:56

C++
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Sqrt(x).
Memory Usage: 5.8 MB, less than 74.81% of C++ online submissions for Sqrt(x).

class Solution {
public:
    int mySqrt(int x) {
        // Babylonian
        
        if (x <= 1) return x;
        
        double guess = 1.0 * x / 2;
        double prev = guess + 1;
        double accuracy = 1;
        
        while (prev - guess >= accuracy) {
            prev = guess;
            guess = (prev + (1.0 * x / prev)) / 2;
        }
        return guess;
    }
};

Babylonian Method
https://en.wikipedia.org/wiki/Methods_of_computing_square_roots

익명
작성일 2022.05.25 00:11

Runtime: 85 ms, faster than 75.68% of JavaScript online submissions for Sqrt(x).
Memory Usage: 43.9 MB, less than 37.43% of JavaScript online submissions for Sqrt(x).

var mySqrt = function(x) {
    // input is 7, outcome is ...
    // 1, 2, 3, 4, 5, 6, 7
    // x is zero or all positive, decimals
    // return the square root of x.
    //need to use Math.floor method.
    
    // edge case: 
    if (x < 2) return x;
    
    // declare left, right pointer
    let left = 1;
    let right = x;
    
    // loop: left < right
    while (left < right) {
        let mid = Math.floor((left + right) / 2 );
        
        if (mid * mid === x) return mid;
        else if (mid * mid > x) right = mid;
        else if (mid * mid < x) left = mid+1;
    }
        return left-1;
    
};