Logo
    Logo

    ©️ 2020-2026, Akhil Abraham.

    LinkedInGitHubMediumX
    Akhil Abraham
    Akhil Abraham
    /Posts
    Posts
    /LeetCode
    LeetCode
    /
    LeetCode
    /0069 - Sqrt(x)
    0069 - Sqrt(x)
    0069 - Sqrt(x)
    0069 - Sqrt(x)

    0069 - Sqrt(x)

    Difficulty
    Easy
    Language
    Python
    URL
    https://leetcode.com/problems/sqrtx/

    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)TimeComplexity: O(\log n)TimeComplexity:O(logn)
    SpaceComplexity:O(1)SpaceComplexity: O(1)SpaceComplexity:O(1)

    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(n)TimeComplexity: O(\sqrt{n})TimeComplexity:O(n​)
    SpaceComplexity:O(1)SpaceComplexity: O(1)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()

    """ 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()