Nth Root of a Number using Binary Search

Given a number x and a positive integer n, your task is to find the nth root of x. That is, find a real number r such that rn = x.

You should return the value of r up to a certain precision (for example, 6 decimal places).

• If x = 0, then the nth root is 0.
• If x = 1, the nth root is always 1.
• If n = 1, then the result is just x (because the 1st root of any number is the number itself).
• Return -1 for invalid cases, like x < 0 and even n, or if n ≤ 0.

Understanding the Problem

We are given two numbers: x and n. Our goal is to find the nth root of x, which means finding a number r such that rn = x.

However, in many cases, the exact root may not be an integer or may not exist in the real number system. So, we want to find an approximation with high precision using an efficient algorithm that works for both small and large values of x and n.

To do this efficiently, we use binary search because the function f(r) = rn is monotonic — it increases as r increases.

Step-by-Step Solution with Example

step 1: Understand special cases

Before diving into the binary search logic, we must handle edge cases:

• If x = 0: The result is 0 (since 0 raised to any positive power is 0).
• If x = 1: The result is 1 (since 1 raised to any power is still 1).
• If n = 1: The root of degree 1 is the number itself, so return x.
• If n ≤ 0: The root is not defined or non-standard — return -1.
• If x < 0 and n is even: The root doesn't exist in real numbers — return -1.
• If x < 0 and n is odd: The answer exists and is negative.

step 2: Setup binary search range

We define our search space:

• If x ≥ 1, the nth root lies between 1 and x.
• If 0 < x < 1, the nth root lies between 0 and 1.

Initialize:

low = 0
high = max(1, x)
epsilon = 1e-6  # acceptable precision

step 3: Apply binary search

Repeat the following steps until the high and low pointers are close enough (within epsilon):

while (high - low) > epsilon:
    mid = (low + high) / 2
    if mid**n < x:
        low = mid
    else:
        high = mid

Once the loop ends, either low or high is an accurate enough approximation.

step 4: Return result

We return either low or high as the answer — both are close enough due to the epsilon margin.

step 5: Example – Find cube root of 27

Let’s walk through the algorithm for x = 27 and n = 3 (i.e., find the cube root of 27).

• Initial range: low = 0, high = 27
• Mid = 13.5 → 13.5³ = 2460.375 → Too high → high = 13.5
• Mid = 6.75 → 6.75³ = 307.546875 → Too high → high = 6.75
• Mid = 3.375 → 3.375³ = 38.44 → Still too high → high = 3.375
• Mid = 1.6875 → 1.6875³ = 4.80 → Too low → low = 1.6875
• Keep repeating...
• Eventually we’ll get mid ≈ 3.0 with mid3 ≈ 27

Edge Cases

• Negative inputs with even roots: Example: x = -16, n = 2 → Invalid in real numbers.
• Fractional x: Example: x = 0.008, n = 3 → Root lies between 0 and 1.
• Large x and n: The method works well due to logarithmic time — just ensure high precision (epsilon).

Finally

This solution breaks down the problem clearly and solves it with binary search — a very efficient and beginner-friendly technique for continuous, monotonic functions like rn. By handling special cases and edge cases explicitly, we ensure correctness and robustness.

Always remember to test your logic against different input types: small, large, negative, and fractional values. And tune your precision epsilon based on how accurate the result needs to be.

1. Set the search range from low = 0 to high = x (or 1, whichever is higher).
2. Run a binary search with precision (e.g., 1e-6).
3. At each step, calculate mid and raise it to the power n.
4. If mid^n is close enough to x, return mid.
5. If mid^n is less than x, search in the right half.
6. If mid^n is greater than x, search in the left half.
7. Repeat until the desired precision is achieved.

#include <stdio.h>
#include <math.h>

double nthRoot(double x, int n) {
    if (x == 0) return 0.0;
    double low = 0.0, high = fmax(1.0, x);
    double eps = 1e-6;

    while ((high - low) > eps) {
        double mid = (low + high) / 2.0;
        if (pow(mid, n) < x) low = mid;
        else high = mid;
    }

    return round((low + high) / 2.0 * 1e6) / 1e6;
}

int main() {
    double x = 27;
    int n = 3;
    printf("Nth root is: %.6f\n", nthRoot(x, n));
    return 0;
}

#include <iostream>
#include <cmath>
using namespace std;

double nthRoot(double x, int n) {
    if (x == 0) return 0.0;
    double low = 0, high = max(1.0, x);
    double eps = 1e-6;

    while (high - low > eps) {
        double mid = (low + high) / 2.0;
        double power = pow(mid, n);
        if (power < x) low = mid;
        else high = mid;
    }

    return round((low + high) / 2.0 * 1e6) / 1e6;
}

int main() {
    double x = 27;
    int n = 3;
    cout << "Nth root is: " << nthRoot(x, n) << endl;
    return 0;
}

def nth_root(x, n):
    if x == 0:
        return 0.0

    low = 0.0
    high = max(1.0, x)
    eps = 1e-6

    while (high - low) > eps:
        mid = (low + high) / 2.0
        if mid ** n < x:
            low = mid
        else:
            high = mid

    return round((low + high) / 2.0, 6)

x = 27
n = 3
print("Nth root is:", nth_root(x, n))

public class NthRoot {
  public static double nthRoot(int x, int n) {
    if (x == 0) return 0.0;
    double low = 0, high = Math.max(1, x);
    double eps = 1e-6;

    while ((high - low) > eps) {
      double mid = (low + high) / 2.0;
      double power = Math.pow(mid, n);
      if (power < x) low = mid;
      else high = mid;
    }

    return Math.round((low + high) / 2.0 * 1e6) / 1e6;
  }

  public static void main(String[] args) {
    int x = 27, n = 3;
    System.out.println("Nth root is: " + nthRoot(x, n));
  }
}

function nthRoot(x, n) {
  if (x === 0) return 0.0;
  let low = 0.0;
  let high = Math.max(1.0, x);
  let eps = 1e-6;

  while (high - low > eps) {
    let mid = (low + high) / 2.0;
    let power = Math.pow(mid, n);
    if (power < x) low = mid;
    else high = mid;
  }

  return Number(((low + high) / 2.0).toFixed(6));
}

console.log("Nth root is:", nthRoot(27, 3));

package main

import (
    "fmt"
    "math"
)

func nthRoot(x float64, n int) float64 {
    if x == 0 {
        return 0.0
    }
    low := 0.0
    high := math.Max(1.0, x)
    eps := 1e-6

    for high - low > eps {
        mid := (low + high) / 2.0
        if math.Pow(mid, float64(n)) < x {
            low = mid
        } else {
            high = mid
        }
    }

    return math.Round((low + high) / 2.0 * 1e6) / 1e6
}

func main() {
    x := 27.0
    n := 3
    fmt.Printf("Nth root is: %.6f\n", nthRoot(x, n))
}

fn nth_root(x: f64, n: u32) -> f64 {
    if x == 0.0 {
        return 0.0;
    }
    let mut low = 0.0;
    let mut high = x.max(1.0);
    let eps = 1e-6;

    while high - low > eps {
        let mid = (low + high) / 2.0;
        if mid.powi(n as i32) < x {
            low = mid;
        } else {
            high = mid;
        }
    }
    ((low + high) / 2.0 * 1e6).round() / 1e6
}

fn main() {
    let x = 27.0;
    let n = 3;
    println!("Nth root is: {:.6}", nth_root(x, n));
}

fun nthRoot(x: Double, n: Int): Double {
    if (x == 0.0) return 0.0
    var low = 0.0
    var high = maxOf(1.0, x)
    val eps = 1e-6

    while ((high - low) > eps) {
        val mid = (low + high) / 2.0
        if (Math.pow(mid, n.toDouble()) < x) low = mid
        else high = mid
    }

    return Math.round((low + high) / 2.0 * 1e6) / 1e6
}

fun main() {
    val x = 27.0
    val n = 3
    println("Nth root is: ${nthRoot(x, n)}")
}

import Foundation

func nthRoot(x: Double, n: Int) -> Double {
    if x == 0 { return 0.0 }
    var low = 0.0
    var high = max(1.0, x)
    let eps = 1e-6

    while high - low > eps {
        let mid = (low + high) / 2.0
        if pow(mid, Double(n)) < x {
            low = mid
        } else {
            high = mid
        }
    }

    return round((low + high) / 2.0 * 1e6) / 1e6
}

let x = 27.0
let n = 3
print("Nth root is: \(nthRoot(x: x, n: n))")

function nthRoot(x: number, n: number): number {
  if (x === 0) return 0.0;
  let low = 0.0;
  let high = Math.max(1.0, x);
  let eps = 1e-6;

  while (high - low > eps) {
    let mid = (low + high) / 2.0;
    let power = Math.pow(mid, n);
    if (power < x) low = mid;
    else high = mid;
  }

  return Number(((low + high) / 2.0).toFixed(6));
}

console.log("Nth root is:", nthRoot(27, 3));

Time complexity

Space complexity

O(1)

The algorithm uses only a few variables and no extra memory for computation.