Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. x^n grows with x, so binary search x between 1 and m.
  2. 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);
    }
}

Solve Nth Root of an Integer online · All practice problems