Find the Nth Root of a Number Using Binary Search

Arrays - Binary Search

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

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.

Examples❯

Value (x) Root (n) Output Description
27 3 3.000000 33 = 27, so cube root of 27 is 3
16 4 2.000000 24 = 16, so 4th root is 2
10 3 2.154435 Cube root of 10 is a real number between 2 and 3
1 5 1.000000 1 raised to any power is 1
0 3 0.000000 0 raised to any positive power is 0
7 1 7.000000 1st root of any number is the number itself
0 0 -1 Invalid input: root 0 is not defined
-8 3 -2.000000 Valid: cube root of negative number is negative
-8 2 -1 Invalid: even root of negative number
-1 Empty input is invalid

Solution❯

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.53 = 2460.375 → Too high → high = 13.5
  • Mid = 6.75 → 6.753 = 307.546875 → Too high → high = 6.75
  • Mid = 3.375 → 3.3753 = 38.44 → Still too high → high = 3.375
  • Mid = 1.6875 → 1.68753 = 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.

Algorithm Steps❯

  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.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#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;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(1)If the root is a perfect integer like sqrt(1), it returns quickly.
Average CaseO(log x)Each binary search iteration reduces the range of possible values by half.
Worst CaseO(log x)Precision-based binary search continues until the result is within the specified error margin.

Space Complexity❯

O(1)

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


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...