Find nth root of m
Description
You are given two positive integers n and m. Your task is to find the nth root of m, denoted as n√m.
The nth root of m is defined as an integer x such that x^n = m (i.e., x raised to the power n equals m).
If the nth root is an integer, return that integer. If the nth root is not an integer (i.e., no integer x exists such that x^n = m), return -1.
Examples
Example 1
Input: n = 3, m = 8
Output: 2
Explanation: We need to find the cube root (3rd root) of 8. Since 2³ = 2 × 2 × 2 = 8, the answer is 2.
Example 2
Input: n = 3, m = 9
Output: -1
Explanation: We need the cube root of 9. Let's check: 2³ = 8 (too small) and 3³ = 27 (too large). No integer between 2 and 3 exists, so the 3rd root of 9 is not an integer. Return -1.
Example 3
Input: n = 4, m = 16
Output: 2
Explanation: We need the 4th root of 16. Since 2⁴ = 2 × 2 × 2 × 2 = 16, the answer is 2.
Example 4
Input: n = 2, m = 9
Output: 3
Explanation: The 2nd root (square root) of 9 is 3, since 3² = 9.
Constraints
- 1 ≤ n ≤ 9
- 0 ≤ m ≤ 20
Editorial
Brute Force
Intuition
The simplest approach is to try every integer starting from 1 and compute its nth power. We keep going until the power either equals m (we found the root) or exceeds m (no exact root exists).
Think of it like a combination lock. You know the lock opens when you raise some number to the nth power and get m. You start trying 1, 2, 3, ... and compute the power each time. If you get exactly m, the lock opens. If you overshoot (power > m), the answer doesn't exist.
Special case: if m = 0, the nth root is 0 (since 0^n = 0 for any n ≥ 1). If m = 1, the nth root is 1 (since 1^n = 1 for any n).
Step-by-Step Explanation
Let's trace through with n = 3, m = 8 (finding the cube root of 8):
Step 1: Handle special case. m = 8, not 0, so continue. Start with i = 1.
Step 2: i = 1. Compute 1³ = 1 × 1 × 1 = 1. Is 1 == 8? NO. Is 1 > 8? NO. Continue.
Step 3: i = 2. Compute 2³ = 2 × 2 × 2 = 8. Is 8 == 8? YES! We found the answer.
Step 4: Return 2.
Now let's trace n = 3, m = 9 (cube root of 9):
Step 1: i = 1. 1³ = 1. Not equal to 9. Continue.
Step 2: i = 2. 2³ = 8. Not equal to 9. 8 < 9, so continue.
Step 3: i = 3. 3³ = 27. Not equal to 9. 27 > 9, so the root must be between 2 and 3 — no integer root exists.
Step 4: Return -1.
Linear Search — Computing Powers to Find Cube Root of 8 — We try i = 1, 2, 3, ... computing i^n at each step until we either find an exact match or overshoot.
Algorithm
- If m == 0, return 0 (0^n = 0 for any n ≥ 1).
- Iterate i from 1 upward:
a. Compute power = i^n.
b. If power == m, return i (exact nth root found).
c. If power > m, return -1 (overshot — no integer root exists). - Return -1 (should not reach here).
Code
#include <iostream>
using namespace std;
class Solution {
public:
int nthRoot(int n, int m) {
if (m == 0) return 0;
for (int i = 1; i <= m; i++) {
long long power = 1;
for (int j = 0; j < n; j++) {
power *= i;
if (power > m) break;
}
if (power == m) return i;
if (power > m) return -1;
}
return -1;
}
};class Solution:
def nthRoot(self, n, m):
if m == 0:
return 0
i = 1
while True:
power = i ** n
if power == m:
return i
if power > m:
return -1
i += 1class Solution {
public int nthRoot(int n, int m) {
if (m == 0) return 0;
for (int i = 1; i <= m; i++) {
long power = 1;
for (int j = 0; j < n; j++) {
power *= i;
if (power > m) break;
}
if (power == m) return i;
if (power > m) return -1;
}
return -1;
}
}Complexity Analysis
Time Complexity: O(m^(1/n) × n)
The outer loop runs at most m^(1/n) times (since i^n ≤ m implies i ≤ m^(1/n)). For each candidate, computing i^n takes O(n) time. For the given constraints (m ≤ 20, n ≤ 9), this is very fast — at most about 20 iterations with up to 9 multiplications each.
Space Complexity: O(1)
We use only a few integer variables. No additional data structures are needed.
Why This Approach Is Not Efficient
The linear scan checks every integer from 1 to m^(1/n). While this is fast for the given constraints (m ≤ 20), it doesn't scale. If m were up to 10^18 and n = 2, we'd be checking up to 10^9 values — far too slow.
The key insight is that powers of integers form a monotonically increasing sequence: 1^n, 2^n, 3^n, ... is always sorted in ascending order. This means we're searching for a target value (m) in a sorted sequence — the classic scenario where binary search shines.
Instead of trying every integer one by one, we can check the middle of our range. If mid^n < m, the answer must be in the right half. If mid^n > m, the answer must be in the left half. If mid^n == m, we found it. This reduces the search from O(m^(1/n)) to O(log(m)) candidates, with each candidate taking O(n) to evaluate — giving O(n × log(m)) total.
Optimal Approach - Binary Search
Intuition
Since i^n is a monotonically increasing function for positive integers, we can use binary search on the range [1, m] to find the nth root.
At each step, we pick the middle value mid and compute mid^n:
- If
mid^n == m, we found the exact nth root. Return mid. - If
mid^n < m, the root (if it exists) must be larger. Search the right half: low = mid + 1. - If
mid^n > m, the root (if it exists) must be smaller. Search the left half: high = mid - 1.
If the search space is exhausted (low > high) without finding an exact match, no integer nth root exists — return -1.
Important detail for overflow prevention: When computing mid^n, the intermediate values can become very large if m is large. To prevent overflow, we multiply incrementally and break early if the product exceeds m — there's no need to compute the full power if it already exceeds the target.
This approach is essentially the same as the square root binary search, generalized to any power n.
Step-by-Step Explanation
Let's trace through with n = 3, m = 8 (finding cube root of 8):
Step 1: Initialize low = 1, high = 8.
Step 2: Compute mid = (1 + 8) / 2 = 4. Compute 4³ = 64.
- Is 64 == 8? NO. Is 64 > 8? YES. The root must be smaller.
- Set high = mid - 1 = 3.
Step 3: Compute mid = (1 + 3) / 2 = 2. Compute 2³ = 8.
- Is 8 == 8? YES! We found the exact cube root.
Step 4: Return 2.
Now let's trace n = 3, m = 9 (cube root of 9 — no integer root):
Step 1: Initialize low = 1, high = 9.
Step 2: mid = (1 + 9) / 2 = 5. 5³ = 125 > 9. Set high = 4.
Step 3: mid = (1 + 4) / 2 = 2. 2³ = 8 < 9. Set low = 3.
Step 4: mid = (3 + 4) / 2 = 3. 3³ = 27 > 9. Set high = 2.
Step 5: low (3) > high (2). Loop ends. No exact root found. Return -1.
Binary Search — Finding Cube Root of 8 — Watch how binary search narrows the candidate range by comparing mid^n with m. The search space halves at each step.
Now let's trace the "not found" case: n = 3, m = 9:
Binary Search — No Integer Cube Root of 9 — When no exact integer root exists, binary search exhausts the search space and returns -1. Watch how the range collapses without finding an exact match.
Algorithm
- If m == 0, return 0.
- Initialize low = 1, high = m.
- While low ≤ high:
a. Compute mid = low + (high - low) / 2.
b. Compute power = mid^n (multiply mid by itself n times, with early exit if power exceeds m to prevent overflow).
c. If power == m, return mid (exact nth root found).
d. If power < m, search right: low = mid + 1.
e. If power > m, search left: high = mid - 1. - Return -1 (no integer nth root exists).
Code
#include <iostream>
using namespace std;
class Solution {
public:
int nthRoot(int n, int m) {
if (m == 0) return 0;
int low = 1, high = m;
while (low <= high) {
int mid = low + (high - low) / 2;
// Compute mid^n with overflow prevention
long long power = 1;
bool overflow = false;
for (int i = 0; i < n; i++) {
power *= mid;
if (power > m) {
overflow = true;
break;
}
}
if (!overflow && power == m) {
return mid;
} else if (overflow || power > m) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}
};class Solution:
def nthRoot(self, n, m):
if m == 0:
return 0
low, high = 1, m
while low <= high:
mid = low + (high - low) // 2
power = mid ** n
if power == m:
return mid
elif power < m:
low = mid + 1
else:
high = mid - 1
return -1class Solution {
public int nthRoot(int n, int m) {
if (m == 0) return 0;
int low = 1, high = m;
while (low <= high) {
int mid = low + (high - low) / 2;
// Compute mid^n with overflow prevention
long power = 1;
boolean overflow = false;
for (int i = 0; i < n; i++) {
power *= mid;
if (power > m) {
overflow = true;
break;
}
}
if (!overflow && power == m) {
return mid;
} else if (overflow || power > m) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}
}Complexity Analysis
Time Complexity: O(n × log m)
Binary search runs in O(log m) iterations (each step halves the range [1, m]). At each iteration, computing mid^n takes O(n) multiplications. Total: O(n × log m). For the given constraints (n ≤ 9, m ≤ 20), this is at most about 9 × 5 = 45 operations. Even for large m (e.g., 10^18), log₂(10^18) ≈ 60, so the total would be 9 × 60 = 540 operations — extremely fast.
Space Complexity: O(1)
We use only a few integer variables (low, high, mid, power). No additional data structures are needed. Space usage is constant regardless of input size.