Find nth root of a number

initial

I was practice some live coding interviews when I came across this

input: x = 7, n = 3
output: 1.913

input: x = 9, n = 2
output: 3

even tho u dk Newton's method, you can brute force the approach. We can first find up to what whole number ** n is our guess gonna be the closes to x (target number). For example when x=7 and n=3, whole number 1 is the closes (2 cube 3 = 8 and is bigger than x)

Then, we can calculathe the decimal place by going from 0 to 1 with step of 0.0001 (4 d.p.). If we want precision up to 3 dp. we need to have step of 4 dp and round it up. Or else we will get wrong answer.

ALSO very important and i didnt know is that range() canot have float as step. It must be an integer value. So I did

for i in range(0,10000,1):

and dividied i by 10000 again when i reached the logic. We need to return i-1 cuz our condition is (if whole number + i)n is greater than x, break out of loop. So the answer is before this break happens, which is i-1.

def root(x,n):
    ans, count =0,0.0
    if x==0:
        return 0
    for i in range(x):
        if i**n == x:
            return i
        elif i**n >x:
            ans=i-1
            break
    for i in range(0,10000,1):
        if (ans + i/10000)**n >x:
            return round(ans + (i-1)/10000,3)

print(root(29,3))

time complexity is kinda n and space is 1

binary search

I couldnt even think of binary search. But this is kinda a sorted list where our left pointer is 0 and right pointer is x.
we can reduce it to log n time with binary search.

Instead of manually increasing step by 0.0001, how about we search interval by halving the search range? We first set low as 0 and high as x and precision as 4 dp like before.

Very impt from here, what should i put as while condition? The end condition is when our low and high difference is less than the precision of 4dp because like 5dp then we can round up accurately.

Another impt point is moving the 2 pointers. I thought of low = mid+1 and high = mid-1 but logically, we are gonna miss some possible values if we -1 or +1. We just wnna converge the difference of the 2 pointers to that precision.

def root(x, n):
    if x == 0:
        return 0

    low = 0
    high = max(1, x)  # Handle the case where x is less than 1
    precision = 0.0001

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

    return round((low + high) / 2, 3)

# Example usage
print(root(27, 3))  # Output: 3.0
print(root(16, 4))  # Output: 2.0
print(root(7, 3))