Square root of a real number

Problem

Given a real number n, find the square root of n.

Examples

Example 1

1
2
3


Input: n = 25.0
Output: 5.0
Explanation: The square root of 25.0 is 5.0.

Example 2

1
2
3


Input: n = 2.0
Output: 1.41421356237 (approx)
Explanation: The square root of 2.0 is approximately 1.41421356237.

Solution

Method 1 - Binary Search

To find the square root of a real number n, we can use the Binary Search method due to its efficiency in narrowing down the range step by step. Alternatively, the Newton-Raphson method is also widely used for its iterative approach.

Here is the approach:

Set the initial range from 0 to n (or 0 to 1 if n < 1).
Continuously narrow down the range by checking the middle point.
If mid*mid is close enough to n, return mid.
Adjust the range based on whether mid*mid is greater or smaller than n.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


public class Solution {
    public double sqrt(double n) {
        if (n < 0) {
            throw new IllegalArgumentException("Cannot compute square root of a negative number.");
        }
        
        double low, high;
        if (n < 1) {
            low = n;
            high = 1;
        } else {
            low = 0;
            high = n;
        }
        
        double eps = 1e-10;  // Define the precision
        double mid;
        
        while ((high - low) > eps) {
            mid = (low + high) / 2;
            if (mid * mid > n) {
                high = mid;
            } else {
                low = mid;
            }
        }
        
        return (low + high) / 2;  // Mid point as the approximate square root
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.sqrt(25.0));  // Output: 5.0
        System.out.println(sol.sqrt(2.0));   // Output: 1.41421356237 (approx)
        System.out.println(sol.sqrt(0.25));  // Output: 0.5
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution:
    def sqrt(self, n: float) -> float:
        if n < 0:
            raise ValueError("Cannot compute square root of a negative number.")

        low, high = (n, 1) if n < 1 else (0, n)
        eps = 1e-10  # Define the precision
        
        while (high - low) > eps:
            mid = (low + high) / 2
            if mid * mid > n:
                high = mid
            else:
                low = mid
        
        return (low + high) / 2  # Mid point as the approximate square root

# Test examples
if __name__ == "__main__":
    sol = Solution()
    print(sol.sqrt(25.0))  # Output: 5.0
    print(sol.sqrt(2.0))   # Output: 1.41421356237 (approx)
    print(sol.sqrt(0.25))  # Output: 0.5

Complexity

⏰ Time complexity: O(log(n)) for binary search due to halving the search space with each iteration.
🧺 Space complexity: O(1) as it uses a constant amount of extra space.

Problem#

Examples#

Example 1#

Example 2#

Similar Problem#

Solution#

Method 1 - Binary Search#

Code#

Complexity#