494. Find Nth Root of M (Binary Search on Answer)

Given two integers n and M, find the integer n-th root of M — that is, the integer x such that x raised to the power n equals M. If no such integer exists, return -1. Input: 'n, M'.

Input: 'n, M'.

Output: Integer — the n-th root, or -1.

Examples

Input: 3, 27
Output: 3
Explanation: 3^3 = 27.

Input: 2, 16
Output: 4
Explanation: 4^2 = 16.

Input: 4, 69
Output: -1
Explanation: No integer 4th root.

Constraints

• 1<=n<=30
• 0<=M<=10^9

Asked by