Nth Root of a Number
MediumLargest m with mⁿ ≤ x
Guess the root, raise it to the power, and move your guess higher or lower until it fits.
The idea
mⁿ grows monotonically with m, so binary search the base whose nth power hits x (or the largest that stays below).
1
2
3
4
0
1
2
3
Step 1 of 5. Brute force: try 1, 2, 3, … until kⁿ reaches 27. Values: 1, 2, 3, 4.
1/5
Brute force
timeO(m)spaceO(1)
Count up.
1let k = 1;2while (Math.pow(k, n) < m) k++;3const exact = Math.pow(k, n) === m;4return exact ? k : -1;Input
- array
- [1, 2, 3, 4]
Memory
- k
- —
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- n = 3, m = 27
- Output:
- 3
- Explanation:
- 3^3 = 27 exactly.
Example 2
- Input:
- n = 4, m = 69
- Output:
- -1
- Explanation:
- No integer 4th root of 69 → -1.
Example 3
- Input:
- n = 2, m = 49
- Output:
- 7
- Explanation:
- 7^2 = 49.
Practice this problem:GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.