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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sqrt(x)

Number: 69

Difficulty: Easy

Paid? No

Companies: Amazon, Google, TikTok, Meta, LinkedIn, Microsoft, Grammarly, Bloomberg, tcs, Adobe, Uber, Zoho, Apple, Goldman Sachs, Yahoo, SAP

Problem Description

Given a non-negative integer x, compute and return the square root of x rounded down to the nearest integer. You are not allowed to use any built-in exponent function or operator. For example, if x is 8, the actual square root is approximately 2.82842, and rounding down gives 2.

Key Insights

  • The problem can be solved efficiently using binary search.
  • Instead of iterating from 0 to x, binary search narrows down the candidate square roots quickly.
  • The algorithm should handle edge cases like x = 0 and x = 1.
  • By checking mid * mid against x, we can determine if we need to search in the lower or upper half.

Space and Time Complexity

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

Solution

We use a binary search approach to find the integer square root. Initialize two pointers, low and high, where low is set to 0 and high is set to x. For each iteration, calculate the mid value. If mid squared equals x, we have found the square root. If mid squared is less than x, record mid as a potential answer and move the low pointer to mid + 1. Otherwise, move the high pointer to mid - 1. Continue the search until low exceeds high, then return the last recorded candidate.

Code Solutions

# Binary search solution to find the integer square root
def mySqrt(x):
    # Edge case for small numbers
    if x < 2:
        return x
    
    low, high = 0, x
    ans = 0
    # Binary search loop
    while low <= high:
        mid = (low + high) // 2
        # If mid squared equals x, we found the exact square root
        if mid * mid == x:
            return mid
        # If mid squared is less than x, store mid and search right half
        elif mid * mid < x:
            ans = mid  # candidate answer
            low = mid + 1
        else:
            # If mid squared is more than x, search left half
            high = mid - 1
    return ans

# Example usage:
print(mySqrt(4))  # Output: 2
print(mySqrt(8))  # Output: 2
← Back to All Questions