Practice › Binary Search
Nth Root of an Integer
Medium · Binary Search · Asked at Amazon, Google, TCS, Infosys
Print the integer x such that x^n = m. If no such integer exists, print -1.
Input
A single line: n m.
Output
x or -1.
Constraints
- 1 ≤ n ≤ 30
- 1 ≤ m ≤ 10^9
Binary search x in [1, m]. While computing mid^n, stop multiplying as soon as the product exceeds m — otherwise it overflows.
Example 1
Input
3 27
Output
3
Example 2
Input
4 69
Output
-1
Hints
- x^n grows with x, so binary search x between 1 and m.
- Compute mid^n by repeated multiplication, but stop as soon as the product exceeds m to avoid overflow.
Approach
For a candidate mid, multiply n times and return early with "too big" once the product passes m. Compare: equal → answer found; too big → search left; too small → search right. If the search ends without equality, no integer root exists. The early exit keeps every intermediate value ≤ m · mid, which fits in 64 bits.
Complexity: O(n log m) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
// 1 if mid^n > m, 0 if equal, -1 if smaller
int cmp(long long mid, int n, long long m) {
long long p = 1;
for (int i = 0; i < n; i++) {
p *= mid;
if (p > m) return 1;
}
return p == m ? 0 : -1;
}
int main() {
int n;
long long m;
cin >> n >> m;
long long lo = 1, hi = m;
while (lo <= hi) {
long long mid = (lo + hi) / 2;
int c = cmp(mid, n, m);
if (c == 0) {
cout << mid << "\n";
return 0;
}
if (c > 0) hi = mid - 1;
else lo = mid + 1;
}
cout << -1 << "\n";
return 0;
}Python solution
n, m = map(int, input().split())
lo, hi, ans = 1, m, -1
while lo <= hi:
mid = (lo + hi) // 2
p = mid**n
if p == m:
ans = mid
break
if p > m:
hi = mid - 1
else:
lo = mid + 1
print(ans)Java solution
import java.util.*;
public class Main {
static int cmp(long mid, int n, long m) {
long p = 1;
for (int i = 0; i < n; i++) {
p *= mid;
if (p > m) return 1;
}
return p == m ? 0 : -1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long m = sc.nextLong();
long lo = 1, hi = m;
while (lo <= hi) {
long mid = (lo + hi) / 2;
int c = cmp(mid, n, m);
if (c == 0) {
System.out.println(mid);
return;
}
if (c > 0) hi = mid - 1;
else lo = mid + 1;
}
System.out.println(-1);
}
}