69. Sqrt(x) - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Description:
Given a non-negative integer x, compute and return ⌊√x⌋ (i.e. the greatest integer less than or equal to √x).

For example:

Example 1:

Example 2:

Constraints:

Hint 1:
Consider using binary search to efficiently find the integer square root. The answer lies in the range [0, x] (or [0, x/2] for x ≥ 4).
Hint 2:
During binary search, for a candidate value mid, check whether mid² is less than, equal to, or greater than x. Adjust the search range accordingly.
Hint 3:
An alternative approach is Newton’s method, an iterative method to approximate the square root quickly.

Define the Search Space:
For x ≥ 2, the square root is always less than or equal to x/2. So, set the search boundaries as:
- low = 1
- high = x // 2
Binary Search Loop:
- Compute mid = (low + high) // 2.
- If mid² equals x, return mid.
- If mid² is less than x, update the answer to mid and set low = mid + 1.
- If mid² is greater than x, set high = mid − 1.
- Continue until low > high.
Return the Answer:
Once the loop ends, the candidate stored is the largest integer whose square is ≤ x.

For x = 8:

Initial boundaries: low = 1, high = 8 // 2 = 4.
Iteration 1:
- mid = (1 + 4) // 2 = 2, and 2² = 4 which is less than 8.
- Set candidate = 2, low becomes 3.
Iteration 2:
- mid = (3 + 4) // 2 = 3, and 3² = 9 which is greater than 8.
- Set high to 2.
Loop stops because low (3) > high (2).
Final Answer: 2

Newton's method can be used to iteratively approximate √x by starting with an initial guess and refining it using the formula:

guess = ( guess + x / guess ) / 2

Repeat until the guess stabilizes. Finally, return the integer part of the guess.

Python3

. . . .

Java

. . . .

Time Complexity:
- The binary search algorithm runs in O(log x) time since the search space is halved in each iteration.
Space Complexity:
- O(1) extra space is used.

For x = 16:

Initial Check:
Since 16 ≥ 2, set low = 1 and high = 16 // 2 = 8.
Iteration 1:
- mid = (1 + 8) // 2 = 4
- 4² = 16, which equals x
- Return 4 immediately.
Final Answer: 4

For x = 26:

Initial Check:
Since 26 ≥ 2, set low = 1 and high = 26 // 2 = 13.
Iteration 1:
- mid = (1 + 13) // 2 = 7
- 7² = 49, which is greater than 26, so set high = 6.
Iteration 2:
- mid = (1 + 6) // 2 = 3
- 3² = 9, which is less than 26, so candidate = 3, set low = 4.
Iteration 3:
- mid = (4 + 6) // 2 = 5
- 5² = 25, which is less than 26, so candidate = 5, set low = 6.
Iteration 4:
- mid = (6 + 6) // 2 = 6
- 6² = 36, which is greater than 26, so set high = 5.
Loop Ends:
- Return candidate = 5.

Off-by-One Errors:
Ensure the binary search loop condition is correct (typically while low ≤ high).
Integer Overflow:
In languages like Java, multiplying two integers (mid * mid) may overflow. Casting to long helps avoid this.
Handling Small x Values:
For x < 2, the square root is x itself.