Domain 1EasyCORE

Sqrt(x)

The problem requires computing the integer part of the square root of a non-negative integer `x`. The input is a single integer `x` where `0 <= x <= 231 - 1`. The output should be an integer representing the floor value of the square root of `x`.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Math#Binary Search

69. Sqrt(x)

Model: qwen2.5-coder:14b
Topics: Math,Binary Search
FAANG asked: 1
Acceptance rate: 35.4%


Problem Breakdown

The problem requires computing the integer part of the square root of a non-negative integer x. The input is a single integer x where 0 <= x <= 231 - 1. The output should be an integer representing the floor value of the square root of x.

Inputs:

  • A non-negative integer x

Outputs:

  • An integer that is the floor value of the square root of x

Implicit Constraints/Edge Cases:

  • If x is 0, the output should be 0.
  • If x is 1, the output should be 1.
  • For large values of x, the computation must handle integer overflow carefully.

Intuition

A brute-force approach would involve iterating from 0 to x and checking if the square of the current number equals x. However, this approach has a time complexity of O(x), which is inefficient for large values of x.

A better approach involves using binary search. The key insight is that the square root function is monotonically increasing, meaning that as x increases, its square root also increases. This property allows us to efficiently narrow down the possible range of the square root using binary search.

Approach

  1. Initialize Pointers: Set two pointers, left to 0 and right to x.
  2. Binary Search Loop:
    • Calculate the middle point mid as (left + right) // 2.
    • If mid * mid is equal to x, return mid.
    • If mid * mid is less than x, move the left pointer to mid + 1.
    • If mid * mid is greater than x, move the right pointer to mid - 1.
  3. Return Result: After exiting the loop, return right as the floor value of the square root.

This approach leverages binary search to achieve a time complexity of O(log x).

Complexity Analysis

  • Time Complexity: O(log x) because we are effectively halving the search space in each iteration.
  • Space Complexity: O(1) since we are using only a constant amount of extra space for variables.

Solution

def mySqrt(x: int) -> int:
    if x == 0 or x == 1:
        return x
    
    left, right = 0, x
    while left <= right:
        mid = (left + right) // 2
        if mid * mid == x:
            return mid
        elif mid * mid < x:
            left = mid + 1
        else:
            right = mid - 1
    
    return right

Edge Cases Handled

  • x = 0: The function returns 0 immediately.
  • x = 1: The function returns 1 immediately.
  • Large values of x: The binary search ensures that the computation remains efficient even for large inputs, as it reduces the number of iterations significantly compared to a linear approach.