Find Nth Root of M

Easy
1396.

Find Nth Root of M

Find Nth Root of M is an easy coding problem on math and binary search, asked in Amazon, Google, TCS and Directi interviews.

Given two positive integers n and m, return the positive integer r with r^n = m — the integer n-th root of m.

If m is not the n-th power of any integer, return -1.

Example 1

Input
n = 3, m = 27
Output
3
Explanation
3 · 3 · 3 = 27.

Example 2

Input
n = 4, m = 69
Output
-1
Explanation
2^4 = 16 and 3^4 = 81, so 69 has no integer fourth root.

Example 3

Input
n = 1, m = 14
Output
14

Constraints

  • 1 <= n <= 30
  • 1 <= m <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number} m
 * @return {number}
 */
var nthRoot = function(n, m) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find Nth Root of M — Solution in Python, Java & C++

Find Nth Root of M solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Find Nth Root of M is an easy coding problem on math and binary search, asked in Amazon, Google, TCS and Directi interviews.

  • Difficulty: Easy
  • Topics: Math, Binary Search
  • Asked at: Amazon, Google, TCS, Directi
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given two positive integers n and m, return the positive integer r with r^n = m — the integer n-th root of m.

If m is not the n-th power of any integer, return -1.

Example 1

Input: n = 3, m = 27
Output: 3
Explanation: 3 · 3 · 3 = 27.

Example 2

Input: n = 4, m = 69
Output: -1
Explanation: 2^4 = 16 and 3^4 = 81, so 69 has no integer fourth root.

Example 3

Input: n = 1, m = 14
Output: 14

Constraints

  • 1 <= n <= 30
  • 1 <= m <= 10^9

Hints for Find Nth Root of M

  1. Hint 1

    r^n grows with r, so the candidates 1, 2, …, m are sorted by their n-th power.

  2. Hint 2

    Binary-search r in [1, m], comparing mid^n with m.

  3. Hint 3

    Compute mid^n by repeated multiplication and stop as soon as the product passes m — that keeps it from overflowing (or from running 30 multiplications of a huge number).

How to solve Find Nth Root of M

Binary search over the root. For a candidate mid, compare mid^n with m: equal means found, smaller means the root is larger, larger means it is smaller. The power is built one factor at a time with an early exit once it exceeds m.

Approach

  1. Set lo = 1, hi = m.
  2. While lo <= hi: take mid, and multiply p = 1 by mid up to n times, breaking as soon as p > m.
  3. If p == m return mid; if p < m set lo = mid + 1; otherwise hi = mid - 1.
  4. If the loop ends, no integer root exists: return -1.

Why it works

For a fixed n >= 1, r -> r^n is strictly increasing on positive integers, so at most one r has r^n = m, and comparing at mid tells which half could contain it. The early exit is safe because once the partial product exceeds m, further multiplication by mid >= 1 keeps it above m.

Complexity

  • Time — O(n · log m)
  • Space — O(1)

Pitfalls

  • Floating-point pow(m, 1/n) can land just below an exact root (e.g. 0.999…); never trust it without an exact integer check.
  • Without the early exit, mid^n overflows 64-bit integers immediately for large mid.
  • m = 1 has root 1 for every n.

Reference solution

Python

def nthRoot(n: int, m: int) -> int:
    lo, hi = 1, m
    while lo <= hi:
        mid = (lo + hi) // 2
        p = 1
        for _ in range(n):
            p *= mid
            if p > m:
                break
        if p == m:
            return mid
        if p < m:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Java

public static int nthRoot(int n, int m) {
    long lo = 1, hi = m;
    while (lo <= hi) {
        long mid = lo + (hi - lo) / 2;
        long p = 1;
        for (int i = 0; i < n; i++) {
            p *= mid;
            if (p > m) break;
        }
        if (p == m) return (int) mid;
        if (p < m) lo = mid + 1; else hi = mid - 1;
    }
    return -1;
}

C++

int nthRoot(int n, int m) {
    long long lo = 1, hi = m;
    while (lo <= hi) {
        long long mid = lo + (hi - lo) / 2;
        long long p = 1;
        for (int i = 0; i < n; i++) {
            p *= mid;
            if (p > m) break;
        }
        if (p == m) return (int)mid;
        if (p < m) lo = mid + 1; else hi = mid - 1;
    }
    return -1;
}

JavaScript

var nthRoot = function(n, m) {
    var lo = 1, hi = m;
    while (lo <= hi) {
        var mid = lo + Math.floor((hi - lo) / 2);
        var p = 1;
        for (var i = 0; i < n; i++) {
            p *= mid;
            if (p > m) break;
        }
        if (p === m) return mid;
        if (p < m) lo = mid + 1; else hi = mid - 1;
    }
    return -1;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue

Learn the technique: Binary Search