459. Check if N-th Root of M Exists

Given two integers n and m, return true if there exists an integer x such that x^n == m. Otherwise return false. Do not use built-in power or root functions. Solve in O(log m).

Input: Integers n (the root degree) and m (the value).

Output: true if integer nth root of m exists, false otherwise.

Examples

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

Input: 2, 14
Output: false
Explanation: No integer r with r^2=14.

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

Constraints

• 2 <= n <= 10
• 0 <= m <= 10^9

Asked by