⬅ Previous Topic
Square Root using Binary SearchNext Topic ⮕
Koko Eating Bananas⬅ Previous Topic
Square Root using Binary SearchNext Topic ⮕
Koko Eating BananasTopic Contents
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).
x = 0
, then the nth root is 0.x = 1
, the nth root is always 1.n = 1
, then the result is just x
(because the 1st root of any number is the number itself).-1
for invalid cases, like x < 0
and even n
, or if n ≤ 0
.low = 0
to high = x
(or 1, whichever is higher).1e-6
).mid
and raise it to the power n
.mid^n
is close enough to x
, return mid
.mid^n
is less than x
, search in the right half.mid^n
is greater than x
, search in the left half.def nth_root(x, n):
if x == 0:
return 0.0
low = 0.0
high = max(1.0, x)
eps = 1e-6 # Precision threshold
while (high - low) > eps:
mid = (low + high) / 2.0
if mid ** n < x:
low = mid # Mid is too small
else:
high = mid # Mid is too big or correct
return round((low + high) / 2.0, 6)
x = 27
n = 3
print("Nth root is:", nth_root(x, n))
Case | Time Complexity | Explanation |
---|---|---|
Best Case | O(1) | If the root is a perfect integer like sqrt(1), it returns quickly. |
Average Case | O(log x) | Each binary search iteration reduces the range of possible values by half. |
Worst Case | O(log x) | Precision-based binary search continues until the result is within the specified error margin. |
O(1)
Explanation: The algorithm uses only a few variables and no extra memory for computation.
⬅ Previous Topic
Square Root using Binary SearchNext Topic ⮕
Koko Eating BananasYou can support this website with a contribution of your choice.
When making a contribution, mention your name, and programguru.org in the message. Your name shall be displayed in the sponsors list.