RTE logo
← Back to DSA map
Binary Search

Square Root without Math.sqrt

Find a square root to 2 decimal places by repeatedly halving the range.

Easy

Problem

Write a function that calculates the square root of a non-negative number without using Math.sqrt(). The result must be accurate to 2 decimal places.

  • Do not use Math.sqrt() or ** 0.5.
  • Return NaN for negative input.
  • The result must be accurate to 2 decimal places, including for numbers below 1.

Examples

Input: n = 144
Output: 12
Input: n = 2
Output: 1.41
Input: n = 0.25
Output: 0.5
For numbers below 1, the root is bigger than the number.

Approach

Time O(log(n / ε))Space O(1)
  1. The root lies between 0 and max(1, n). The max matters: for n < 1 the root is larger than n, so a range of [0, n] would miss it.
  2. Take mid of the range. If mid² < n the root is above mid, so move low up; otherwise move high down.
  3. Each step cuts the range in half, so the answer gets one bit more precise every time. 100 halvings is far more than 2 decimal places need.
  4. Round the result to 2 decimals.

Common mistakes

  • Using [0, n] as the starting range fails for n < 1.
  • Stopping when |n - guess²| is small is not the same as the guess being accurate to 2 decimals - check the precision of the guess itself.
  • Looping until high - low is tiny can run forever on huge numbers, because decimals in a computer cannot get that close together. Running a fixed number of steps avoids that.

Solution

The same approach in JavaScript, Python, and Java. Each is a complete program that prints the examples above - JavaScript runs here, so edit it and try your own input.

Edit and run it here

JavaScript solution

Loading...

Output

Run code to see output...

Comments

Sign in to leave a comment. Your name and photo come from Google; nothing else is shared.

Loading comments...