{x}
blog image

Sqrt(x)

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.

You must not use any built-in exponent function or operator.

  • For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.

 

Example 1:

Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.

Example 2:

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.

 

Constraints:

  • 0 <= x <= 231 - 1

Solution Explanation for Sqrt(x)

The problem requires finding the integer square root of a non-negative integer x without using built-in exponent functions. The most efficient approach is using Binary Search.

Algorithm (Binary Search):

  1. Initialization: Set the left boundary l to 0 and the right boundary r to x. This establishes the search space.

  2. Iteration: While l is less than r, perform the following steps:

    • Calculate the middle value mid = (l + r + 1) // 2 (integer division). We add 1 to ensure that if l and r are adjacent, the larger value is chosen.
    • Comparison: Compare mid with x / mid. There are two possibilities:
      • mid > x / mid: This means mid * mid > x, which implies that the square root is smaller than mid. Thus, update the right boundary: r = mid - 1.
      • mid <= x / mid: This means mid * mid <= x, which implies that the square root is at least mid. Update the left boundary: l = mid.

  3. Result: After the loop terminates, l will hold the floor of the square root of x. Return l.

Why Binary Search?

Binary search is efficient because it repeatedly halves the search space. This results in logarithmic time complexity. A linear search would be significantly slower for large values of x.

Code Examples:

The code examples below implement the binary search algorithm in several programming languages. Note the subtle differences in how integer division and bitwise right shifts are handled across languages. The >>> operator in Java and some other languages ensures an unsigned right shift (important for negative numbers, though not directly relevant here since x is non-negative). In Python, // performs integer division. In C++, 1ll is used to explicitly promote l+r+1 to long long, preventing overflow before division.

The Go implementation uses the sort.Search function which is a highly optimized binary search function. This simplifies the implementation significantly.

Time Complexity: O(log x) - The search space is halved in each iteration of the binary search.

Space Complexity: O(1) - The algorithm uses only a constant amount of extra space.

Example Walkthrough (x = 8):

  1. l = 0, r = 8
  2. mid = (0 + 8 + 1) // 2 = 4 4 > 8 // 4 = 2 (false) so l = 4
  3. l = 4, r = 8
  4. mid = (4 + 8 + 1) // 2 = 6 6 > 8 // 6 = 1 (true) so r = 5
  5. l = 4, r = 5
  6. mid = (4 + 5 + 1) // 2 = 5 5 > 8 // 5 = 1 (true) so r = 4
  7. l = 4, r = 4 Loop terminates.
  8. l = 2 is returned.