Square root of a real number

Problem

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

Examples

Example 1

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

Example 2

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

Java

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
    }
}

C++

#include <stdexcept>
#include <algorithm>

class Solution {
 public:
  double sqrt(double n, double eps = 1e-10) {
    if (n < 0) throw std::domain_error("Cannot compute square root of a negative number.");
    double low, high;
    if (n < 1.0) { low = n; high = 1.0; } else { low = 0.0; high = n; }
    while ((high - low) > eps) {
      double mid = (low + high) / 2.0;
      if (mid * mid > n) high = mid; else low = mid;
    }
    return (low + high) / 2.0;
  }
};

Python

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.

Method 2 — Newton-Raphson method

Intuition

If x is an approximation of sqrt(n), then n/x is an approximation from the other side. Averaging them, (x + n/x)/2, produces a better approximation. Repeating this update quickly converges to sqrt(n).

Approach

1. Handle n < 0 (undefined for real square root) and trivial values (n == 0 or n == 1).
2. Initialize x = n / 2 (or x = n for n < 1) as a starting guess.
3. Repeat until convergence (difference between x*x and n is below epsilon):
   1. Compute x = (x + n / x) / 2.
4. Return x.

Code

C++

class Solution {
 public:
  double sqrt(double n, double eps = 1e-7) {
    if (n < 0) throw std::domain_error("n must be non-negative");
    if (n == 0.0 || n == 1.0) return n;
    double x = (n >= 1.0) ? n / 2.0 : n;
    while (std::abs(x * x - n) > eps) {
      x = (x + n / x) / 2.0;
    }
    return x;
  }
};

Go

package main

import (
  "errors"
  "math"
)

func sqrt(n, eps float64) (float64, error) {
  if n < 0 { return 0, errors.New("n must be non-negative") }
  if n == 0 || n == 1 { return n, nil }
  x := n
  if n >= 1 { x = n / 2 }
  for math.Abs(x*x-n) > eps {
    x = (x + n/x) / 2
  }
  return x, nil
}

Java

class Solution {
  public double sqrt(double n, double eps) {
    if (n < 0) throw new IllegalArgumentException("n must be non-negative");
    if (n == 0 || n == 1) return n;
    double x = (n >= 1.0) ? n / 2.0 : n;
    while (Math.abs(x * x - n) > eps) {
      x = (x + n / x) / 2.0;
    }
    return x;
  }
}

Kotlin

object Solution {
  fun sqrt(n: Double, eps: Double = 1e-7): Double {
    require(n >= 0) { "n must be non-negative" }
    if (n == 0.0 || n == 1.0) return n
    var x = if (n >= 1.0) n / 2.0 else n
    while (kotlin.math.abs(x * x - n) > eps) {
      x = (x + n / x) / 2.0
    }
    return x
  }
}

Python

class Solution:
    def sqrt(self, n: float, eps: float = 1e-7) -> float:
        if n < 0:
            raise ValueError('n must be non-negative')
        if n == 0.0 or n == 1.0:
            return n
        x = n / 2.0 if n >= 1.0 else n
        while abs(x * x - n) > eps:
            x = (x + n / x) / 2.0
        return x

Rust

pub struct Solution;
impl Solution {
  pub fn sqrt(n: f64, eps: f64) -> f64 {
    if n < 0.0 { panic!("n must be non-negative") }
    if n == 0.0 || n == 1.0 { return n }
    let mut x = if n >= 1.0 { n / 2.0 } else { n };
    while (x * x - n).abs() > eps {
      x = (x + n / x) / 2.0;
    }
    x
  }
}

Complexity

• ⏰ Time complexity: O(k) where k is the number of iterations required to reach epsilon. Newton's method converges quadratically, so k is typically very small.
• 🧺 Space complexity: O(1).