<jupyter_start><jupyter_text>Implement int sqrt(int x).Compute and return the square root of x, where x is guaranteed to be a non-negative integer.Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.Example 1:    Input: 4    Output: 2Example 2:    Input: 8    Output: 2    Explanation: The square root of 8 is 2.82842..., and since                  the decimal part is truncated, 2 is returned.<jupyter_code>class Solution:
    def mySqrt(self, x: int) -> int:
        import math
        return math.floor(x ** 0.5)
    
# test
x = 8
Solution().mySqrt(x)
# binary search
class Solution:
    def mySqrt(self, x: int) -> int:
        if x==1: 
            return 1 
        l, r = 0, x
        while l <= r:
            mid = (r+l)//2
            if mid * mid <= x < (mid+1)*(mid+1):
                return mid
            elif x < mid * mid:
                r = mid
            else:
                l = mid
                
# test
x = 8
Solution().mySqrt(x)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.09640831758034027, 'fraction_numerical': 0.022684310018903593, 'mean_word_length': 1.839142091152815, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '416252', 'license': 'MIT', 'n_tokens_mistral': 351, 'n_tokens_neox': 317, 'n_words': 126, 'path': 'DSA/math/mySqrt.ipynb', 'repo_name': 'lance-lh/Data-Structures-and-Algorithms', 'size': '1058'}