Solution 1 - Binary Search

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. Use binary search over the range [0, x]. At each step, compute the square of the midpoint. If it equals x, return mid. If it's less than x, move the left pointer up and track mid as the best candidate so far. If it's greater, move the right pointer down.

TimeComplexity: O(\log n)

SpaceComplexity: O(1)

""" 0069.1 - Sqrt(x) - Solution 1 - Binary Search """

#####################################################################################
# Imports
#####################################################################################


#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def mySqrt(self, x: int) -> int:
        """Sqrt(x) Function"""
        if x < 2:
            return x

        left, right = 1, x // 2
        result = 0

        while left <= right:
            mid = left + (right - left) // 2
            square = mid * mid

            if square == x:
                return mid
            elif square < x:
                result = mid
                left = mid + 1
            else:
                right = mid - 1

        return result


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().mySqrt(4))   # 2
    print(Solution().mySqrt(8))   # 2
    print(Solution().mySqrt(0))   # 0
    print(Solution().mySqrt(1))   # 1
    print(Solution().mySqrt(16))  # 4


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 2 - Linear Search

Start from 0 and increment upward. At each step, check if (i + 1) * (i + 1) would exceed x. If so, i is the floor of the square root. This is the brute force approach that checks every integer sequentially.

TimeComplexity: O(\sqrt{n})

SpaceComplexity: O(1)

""" 0069.2 - Sqrt(x) - Solution 2 - Linear Search """

#####################################################################################
# Imports
#####################################################################################


#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def mySqrt(self, x: int) -> int:
        """Sqrt(x) Function"""
        i = 0

        while (i + 1) * (i + 1) <= x:
            i += 1

        return i


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().mySqrt(4))   # 2
    print(Solution().mySqrt(8))   # 2
    print(Solution().mySqrt(0))   # 0
    print(Solution().mySqrt(1))   # 1
    print(Solution().mySqrt(16))  # 4


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

0069 - Sqrt(x)

Solution 1 - Binary Search

Solution 2 - Linear Search