# Find Nth root using Binary search.

[Question]: Given two numbers N and M, find the Nth root of M. The nth root of a number M is defined as a number X when raised to the power N equals M. If the ‘nth root is not an integer, return -1.

```Example 1:
Input Format: N = 3, M = 27
Result: 3
Explanation: The cube root of 27 is equal to 3.

Example 2:
Input Format: N = 4, M = 69
Result: -1
Explanation: The 4th root of 69 does not exist. So, the answer is -1. however 64 with cube root 3 possible.```
``````// TC: O(lon(N))
// SC: O(1)
func getMidMultiply(_ mid: Int, _ n: Int, _ m: Int) ->Int {
var ans = 1
for _ in 1...n {
ans = ans * mid
if (ans > m) {
return 2
}
}
if (ans == m) { return 1}// if we got th exact match return as 1 hence we got as a mid element
return 0
}

func NthRoot(_ n: Int, _ m: Int) ->Int {
var low = 1
var high = m
while low <= high {
let mid = (low + high) / 2
let midN = getMidMultiply(mid, n, m)// Find perfect square
if midN == 1 {// Got perfect square
return mid
} else if midN == 0 {// discard first half
low = mid + 1
} else {// discard second half
high = mid - 1
}
}
return -1
}

let firstIp = 3
let secondIp = 27
let opRoot = NthRoot(firstIp, secondIp)
print("The answer is: ", opRoot)// 4 because 3*3*3 = 27``````