N-th Root of a Number

New·Medium·Binary Search

Exact integer root, or -1 if there is none

Asked at:AmazonMicrosoftAdobe

Practice mode

Step

Initialization

Look for an integer x with x^3 = 27, searching candidates 1…27.

Recursion workspace

Binary Search on the Answer

Step 1 / 7init

100%

low

high

Explanation

Raising to a fixed power is increasing, so the candidates 1…27 split cleanly into "too small" and "too big" — binary search can find the boundary, and the exact root if there is one.

step 1 / 7

Space play← → stepHome reset

TimeO(log M · log N)·SpaceO(1)

Binary Search on the Answer

1function helperFunc(mid, n, m) {
2  let ans = 1, base = mid;
3 
4  // Fast exponentiation, bailing out early
5  while (n > 0) {
6    if (n % 2 === 1) {
7      ans *= base;
8      if (ans > m) return 2;   // overshoots
9      n--;
10    } else {
11      n = Math.floor(n / 2);
12      base *= base;//N: 3M: 27low: 1high: 27
13      if (base > m) return 2;
14    }
15  }
16  if (ans === m) return 1;     // exact
17  return 0;                    // too small
18}
19 
20function NthRoot(N, M) {
21  let low = 1, high = M;
22 
23  while (low <= high) {
24    const mid = Math.floor((low + high) / 2);
25    const midN = helperFunc(mid, N, M);
26 
27    if (midN === 1) return mid;
28    else if (midN === 0) low = mid + 1;
29    else high = mid - 1;
30  }
31  return -1;
32}

M27

low1

high27

Command Palette

N-th Root of a Number

N-th Root of a Number