You are given 2 numbers (n , m); the task is to find ^{n}√m (n^{th} root of m).
 
Example 1:
Input: n = 2, m = 9
Output: 3
Explanation: 3^{2} = 9
Example 2:
Input: n = 3, m = 9
Output: -1
Explanation: 3rd root of 9 is not
integer.
 
Your Task:
You don't need to read or print anyhting. Your task is to complete the function NthRoot() which takes n and m as input parameter and returns the nth root of m. If the root is not integer then returns -1.
 
Expected Time Complexity: O(n* log(m))
Expected Space Complexity: O(1)
 
Constraints:
1 <= n <= 30
1 <= m <= 10^{9}

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Starter code: #User function Template for python3

class Solution:
	def NthRoot(self, n, m):
		# Code here

Solutions:
class Solution:

	def NthRoot(self, n, m):
		low = 1
		high = m
		while low <= high:
			mid = (low + high) // 2
			if pow(mid, n) == m:
				return mid
			if pow(mid, n) < m:
				low = mid + 1
			else:
				high = mid - 1
		return -1


import math

class Solution:

	def NthRoot(self, n, m):
		result = round(math.pow(m, 1 / n))
		if math.pow(result, n) != m:
			result = -1
		return result


class Solution:

	def NthRoot(self, n, m):
		l = 1
		r = m
		while l <= r:
			mid = l + (r - l) // 2
			target = mid ** n
			if target == m:
				return mid
			elif target < m:
				l = mid + 1
			else:
				r = mid - 1
		return -1


class Solution:

	def NthRoot(self, n, m):
		if m == 0:
			return 0
		if n == 1:
			return m
		(low, high) = (0, max(1, m))
		while low <= high:
			mid = (low + high) // 2
			if mid ** n == m:
				return mid
			elif mid ** n < m:
				low = mid + 1
			else:
				high = mid - 1
		return -1


class Solution:

	def NthRoot(self, n, m):
		(i, j) = (0, m)
		while i <= j:
			mid = i + j >> 1
			p = mid ** n
			if p == m:
				return mid
			if p < m:
				i = mid + 1
			else:
				j = mid - 1
		return -1


class Solution:

	def NthRoot(self, n, m):
		(left, right) = (1, m)
		while left <= right:
			mid = (left + right) // 2
			if mid ** n == m:
				return mid
			elif mid ** n > m:
				right = mid - 1
			else:
				left = mid + 1
		return -1


class Solution:

	def NthRoot(self, n, m):
		l = 1
		h = m
		while h >= l:
			mid = (l + h) // 2
			res = pow(mid, n)
			if res == m:
				return mid
			elif res > m:
				h = mid - 1
			else:
				l = mid + 1
		return -1


class Solution:

	def NthRoot(self, n, m):
		if n == 1 or m == 1:
			return m
		if n == m:
			return -1
		l = int(m / 2) + 1
		for i in range(1, l):
			x = i ** n
			if x == m:
				return i
			elif x > m:
				break
		return -1


class Solution:

	def NthRoot(self, n, m):
		if n == 1 or m == 1:
			return m
		if n >= m:
			return -1
		start = 1
		end = m
		while int(start) != int(end):
			mid = (start + end) / 2
			if mid ** n == m:
				return int(mid)
			elif mid ** n > m:
				end = mid
			else:
				start = mid
		return -1


class Solution:

	def NthRoot(self, n, m):
		s = 1
		e = m
		if n == 1 or m == 1:
			return m
		if n >= m:
			return -1
		while int(s) != int(e):
			mid = (s + e) / 2
			if mid ** n == m:
				return int(mid)
			if mid ** n < m:
				s = mid
			else:
				e = mid
		return -1


class Solution:

	def NthRoot(self, n, m):
		(l, r) = (1, m)
		while l < r:
			mid = l + (r - l + 1) // 2
			root = mid ** n
			if root <= m:
				l = mid
			else:
				r = mid - 1
		if l ** n == m:
			return l
		else:
			return -1


class Solution(object):

	def NthRoot(self, n, m):

		def power(power, num):
			val = 1
			for _ in range(power):
				val *= num
			return val
		(left, right) = (1, m)
		while left <= right:
			mid = (left + right) // 2
			val = power(n, mid)
			if val == m:
				return mid
			elif val > m:
				right = mid - 1
			else:
				left = mid + 1
		return -1


class Solution:

	def NthRoot(self, n, m):
		i = 1
		j = m
		while i <= j:
			mid = (i + j) // 2
			if mid ** n == m:
				return mid
			elif mid ** n > m:
				j = mid - 1
			else:
				i = mid + 1
		return -1


class Solution:

	def NthRoot(self, n, m):
		(low, high) = (1, m)
		res = -1
		while low <= high:
			mid = (low + high) // 2
			val = mid ** n
			if val == m:
				return mid
			elif val < m:
				low = mid + 1
				res = mid
			else:
				high = mid - 1
		return res if res ** n == m else -1


class Solution:

	def NthRoot(self, n, m):
		left = 1
		right = m
		while left <= right:
			mid = (left + right) // 2
			ts = 1
			for _ in range(n):
				ts *= mid
			if ts == m:
				return mid
			if ts > m:
				right = mid - 1
			else:
				left = mid + 1
		return -1


class Solution:

	def NthRoot(self, n, m):
		i = 1
		ans = 1
		while ans <= m:
			i += 1
			ans = i ** n
		if (i - 1) ** n == m:
			return i - 1
		return -1


class Solution:

	def NthRoot(self, n, m):
		for i in range(m + 1):
			data_ = i ** n
			if data_ == m:
				return i
			elif data_ > m:
				return -1
			else:
				continue


class Solution:

	def NthRoot(self, n, m):
		lo = 1
		hi = m

		def pow(mid, n):
			ans = 1
			for i in range(n):
				ans = ans * mid
			return ans
		while lo <= hi:
			mid = (lo + hi) // 2
			some = pow(mid, n)
			if some == m:
				return mid
			if some > m:
				hi = mid - 1
			else:
				lo = mid + 1
		return -1


class Solution:

	def NthRoot(self, n, m):
		s = 1
		e = m
		mid = 0
		while s <= e:
			mid = (s + e) // 2
			prod = float(m)
			for i in range(1, n + 1):
				prod = prod / mid
			if prod == 1:
				return mid
			elif prod < 1:
				e = mid - 1
			else:
				s = mid + 1
		return -1


class Solution:

	def NthRoot(self, n, m):
		t = round(m ** (1 / n)) ** n
		if t == m:
			return round(m ** (1 / n))
		return -1


class Solution:

	def getNthPower(self, n, m):
		prod = 1
		for i in range(n):
			prod = prod * m
		return prod

	def NthRoot(self, n, x):
		(l, r, mid) = (0, x, 0)
		while l <= r:
			mid = (l + r) // 2
			prod = self.getNthPower(n, mid)
			if prod == x:
				return mid
			elif prod > x:
				r = mid - 1
			else:
				l = mid + 1
		return -1


class Solution:

	def NthRoot(self, n, m):
		import math
		root = math.pow(m, 1 / n)
		if abs(root - round(root)) <= 1e-09:
			return round(root)
		else:
			return -1


class Solution:

	def NthRoot(self, n, m):
		l = 1
		h = m
		while h >= l:
			k = (l + h) // 2
			if k ** n == m:
				return k
			if k ** n > m:
				h = k - 1
			else:
				l = k + 1
		return -1


class Solution:

	def NthRoot(self, n, m):
		low = 1
		high = m
		while low <= high:
			mid = (low + high) // 2
			num = 1
			for i in range(n):
				num *= mid
			if num > m:
				high = mid - 1
			elif num < m:
				low = mid + 1
			else:
				return mid
		return -1


class Solution:

	def NthRoot(self, n, m):
		if m == 1 or n == 1:
			return m
		start = 0
		end = m >> 1
		while start <= end:
			mid = start + end >> 1
			if mid ** n == m:
				return mid
			if mid ** n < m:
				start = mid + 1
			else:
				end = mid - 1
		return -1


class Solution:

	def NthRoot(self, n, m):
		nu = m ** (1 / n)
		if (round(nu) ** n) ** (1 / n) == nu:
			return round(nu)
		else:
			return -1


class Solution:

	def NthRoot(self, n, x):
		l = 0
		r = x
		res = -1
		while l <= r:
			mid = (l + r) // 2
			s = mid ** n
			if s == x:
				return mid
			if s > x:
				r = mid - 1
			else:
				res = mid
				l = mid + 1
		return -1


class Solution:

	def NthRoot(self, n, m):
		low = 1
		high = m
		while low <= high:
			mid = (low + high) // 2
			if pow(mid, n) == m:
				return mid
			if pow(mid, n) < m:
				low = mid + 1
			else:
				high = mid - 1
		return -1

	def multiply(self, num, n):
		ans = 1
		for i in range(1, n + 1):
			ans = ans * num
		return ans


class Solution:

	def NthRoot(self, n, m):
		x = m ** (1 / n)
		if int(x) == x:
			x = int(x)
			return x
		else:
			x = round(x)
			if x ** n == m:
				return x
			else:
				return -1


class Solution:

	def NthRoot(self, n, m):
		for i in range(31):
			if i ** n == m:
				return i
		return -1


from math import floor

class Solution:

	def NthRoot(self, n, m):
		(low, high) = (1, m)
		while low <= high:
			mid = (low + high) // 2
			res = pow(mid, n)
			if res == m:
				return mid
			elif res < m:
				low = mid + 1
			else:
				high = mid - 1
		return -1


from math import floor

class Solution:

	def NthRoot(self, n, m):

		def multiply(num, n):
			ans = 1
			for _ in range(n):
				ans = ans * num
			return ans
		low = 1
		high = m
		while low <= high:
			mid = (low + high) // 2
			res = multiply(mid, n)
			if res == m:
				return mid
			elif res < m:
				low = mid + 1
			else:
				high = mid - 1
		return -1


class Solution:

	def multiply(self, num, n, m):
		ans = num
		for i in range(1, n):
			ans *= num
		return ans

	def NthRoot(self, n, m):
		low = 1
		high = m
		ans = -1
		while low <= high:
			mid = (high + low) // 2
			multiplied = self.multiply(mid, n, m)
			if multiplied == m:
				ans = mid
				break
			elif multiplied < m:
				low = mid + 1
			else:
				high = mid - 1
		return int(ans)


class Solution:

	def NthRoot(self, n, m):
		low = 1
		high = m
		while low <= high:
			mid = low + (high - low) // 2
			power = 1
			for _ in range(n):
				power *= mid
			if power == m:
				return mid
			elif power < m:
				low = mid + 1
			else:
				high = mid - 1
		return -1


import math

class Solution:

	def NthRoot(self, n, m):
		l = 0
		while l ** n <= m:
			l += 1
		temp = (l - 1) ** n
		if temp == m:
			return l - 1
		else:
			return -1


class Solution:

	def NthRoot(self, n, m):
		low = 1
		high = m
		ans = -1
		while low <= high:
			mid = (low + high) // 2
			x = mid
			for i in range(1, n):
				x *= mid
				if x > m:
					break
			if x == m:
				ans = mid
				break
			elif x > m:
				high = mid - 1
			else:
				low = mid + 1
		return ans


class Solution:

	def NthRoot(self, n, m):
		i = 1
		a = 1
		while i <= m:
			i = 1
			for j in range(0, n):
				i = i * a
			if i == m:
				return a
			a = a + 1
		return -1


import math

class Solution:

	def NthRoot(self, n, m):
		s = 1
		end = m
		while s <= end:
			mid = s + (end - s) // 2
			if pow(mid, n) == m:
				return mid
			elif pow(mid, n) < m:
				s = mid + 1
			else:
				end = mid - 1
		return -1


import math

class Solution:

	def NthRoot(self, n, m):
		if m == 1:
			return 1
		if n == 1:
			return m
		(l, h) = (1, m)
		while h - l > 1:
			mid = (l + h) // 2
			if mid ** n == m:
				return mid
			elif mid ** n > m:
				h = mid
			elif mid ** n < m:
				l = mid
		return -1


class Solution:

	def NthRoot(self, n, m):

		def multiply(number, n):
			ans = 1
			for i in range(1, n + 1):
				ans *= number
			return ans
		low = 0
		high = m
		while low <= high:
			mid = (low + high) // 2
			if multiply(mid, n) == m:
				return mid
			if multiply(mid, n) > m:
				high = mid - 1
			else:
				low = mid + 1
		return -1


class Solution:

	def NthRoot(self, n, m):
		a = 0
		while pow(a, n) <= m:
			a += 1
		if pow(a - 1, n) == m:
			return a - 1
		return -1


class Solution:

	def NthRoot(self, n, m):

		def mult(num, n):
			ans = 1
			for i in range(1, n + 1):
				ans = ans * num
			return ans
		l = 0
		r = m
		while l <= r:
			mid = (l + r) // 2
			if mult(mid, n) == m:
				return mid
			if mult(mid, n) < m:
				l = mid + 1
			else:
				r = mid - 1
		return -1