Find Nth Root of M — Easy Problem & Solution

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

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

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More math problems

• Valid Boomerang Easy
• Surface Area of 3D Shapes Easy
• Rectangle Overlap Easy
• Prime Arrangements Easy
• Day of the Week Easy
• Number of Days Between Two Dates Easy