Find the Integer Nth Root of a Number (or Report It Doesn't Exist)
Solve this Problemm and n, find the positive integer x such that x raised to the power n equals m exactly, or return -1 if no such integer exists.
Raising a number to a fixed power is strictly increasing: as x grows, x^n only ever grows with it, never dips back down. That means the candidates 1 through m split cleanly into three zones — too small, exactly right, and too big — in that order, which is exactly the monotonic structure a binary search on the answerBinary Search on the AnswerThe search runs directly over the space of candidate answers rather than over an array. It applies whenever a computed property of the candidate — here, the candidate raised to the n-th power — moves in one direction as the candidate grows. needs: binary search the candidate roots directly, narrowing toward whichever one lands exactly on m — or concluding none does.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ m ≤ 10⁹ - ◆
1 ≤ n ≤ 30
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Try Every Integer From 1 Upward
BruteTry x = 1, 2, 3, ... and raise each one to the n-th power. Stop the moment a candidate's power reaches or exceeds m: if it equals m exactly, that candidate is the answer; if it overshoots, no integer works, since x^n only grows as x grows. Correct, but computing successive powers from scratch for every candidate is wasteful once m and n get large.
O(m · n)O(1)1class Solution {
2 public int nthRoot(int m, int n) {
3 for (int x = 1; x <= m; x++) {
4 long p = power(x, n, m);
5 if (p == m) return x;
6 if (p > m) break;
7 }
8 return -1;
9 }
10
11 private long power(long x, int n, int limit) {
12 long result = 1;
13 for (int i = 0; i < n; i++) {
14 result *= x;
15 if (result > limit) return result;
16 }
17 return result;
18 }
19}Optimal — Binary Search on the Root
Optimalx^n grows strictly with x, so the candidates split cleanly into "too small" (x^n < m), "just right" (x^n = m), and "too big" (x^n > m) — exactly the structure binary search needs. Search the range [1, m]: whenever a candidate's power lands exactly on m, that's the answer; whenever it falls short, search higher; whenever it overshoots, search lower. If the range closes without ever landing exactly on m, no integer n-th root exists.
O(n · log m)O(1)1class Solution {
2 public int nthRoot(int m, int n) {
3 int lo = 1, hi = m;
4 while (lo <= hi) {
5 int mid = lo + (hi - lo) / 2;
6 long p = power(mid, n, m);
7 if (p == m) {
8 return mid;
9 } else if (p < m) {
10 lo = mid + 1;
11 } else {
12 hi = mid - 1;
13 }
14 }
15 return -1;
16 }
17
18 private long power(long x, int n, int limit) {
19 long result = 1;
20 for (int i = 0; i < n; i++) {
21 result *= x;
22 if (result > limit) return result;
23 }
24 return result;
25 }
26}