We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Sqrt(x)

Difficulty: Easy

Problem Description

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.

Key Insights

  • The square root of a number x is the value that, when multiplied by itself, gives x.
  • Since we cannot use built-in exponent functions, we need to find the square root using an algorithmic approach.
  • A binary search can efficiently find the integer square root by narrowing down the possible values.
  • The square root of x will always be in the range of 0 to x.

Space and Time Complexity

Time Complexity: O(log x)
Space Complexity: O(1)

Solution

To solve the problem, we can use a binary search algorithm. The idea is to maintain a search range between 0 and x. We repeatedly check the middle value of the current range:

  1. If the square of the middle value is equal to x, we have found the square root.
  2. If the square is greater than x, we move our search to the left half.
  3. If the square is less than x, we move our search to the right half.
  4. We continue this process until our search range converges.

This approach guarantees that we efficiently find the largest integer whose square is less than or equal to x.

Code Solutions

def mySqrt(x: int) -> int:
    if x < 2:
        return x  # The square root of 0 is 0, and 1 is 1.
    
    left, right = 2, x // 2  # Start binary search from 2 to x // 2
    while left <= right:
        mid = left + (right - left) // 2  # Calculate the middle point
        square = mid * mid  # Square of mid
        
        if square == x:
            return mid  # Exact square root found
        elif square < x:
            left = mid + 1  # Move to the right half
        else:
            right = mid - 1  # Move to the left half
            
    return right  # The largest integer whose square is <= x
← Back to All Questions