Find the 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.

O(1)

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