DSA interview question

Find the Nth Root of a Number

Medium · Algorithms · Topics: binary search, math

The problem

A puzzle app asks players whether a given number m is a perfect n-th power, for example whether 4096 is a perfect 6th power (it is: 4⁶), and if so, what the root is. Floating-point pow(m, 1.0/n) gives answers like 3.9999999 that truncate wrongly. The robust method is binary search on the integer root in [1, m], but computing mid^n can overflow even 64 bits for large n, so the power must be computed with an early exit as soon as it passes m.

Example: n = 3, m = 27 → 3; n = 3, m = 9 → -1 (9 isn't a perfect cube).

Function signature

int nthRoot(int n, int m);  // integer r with r^n == m, or -1 if none (1 <= n <= 30, 1 <= m <= 1e9)

Test cases

Input `(n, m)`	Output	Explanation
(2, 9)	3	3² = 9
(3, 9)	-1	2³ = 8 and 3³ = 27 skip over 9
(3, 27)	3
(1, 14)	14	The first root of m is m
(4, 69)	-1
(6, 4096)	4	4⁶ = 4096
(30, 1)	1	1^30 = 1
(2, 1000000000)	-1	√10⁹ ≈ 31622.8

(Confirm: return the exact integer root or -1; no floating-point pow.)

How interviewers phrase it

"Find the Nth root of M, if it's an integer" (GeeksforGeeks).
Generalises the integer square root; sometimes asked with a required decimal precision instead.

Clarifying questions to ask

Only integer roots, returning -1 otherwise?
Ranges of n and m? (Decides how to avoid overflow.)
If a decimal answer is needed, what precision?

Follow-ups to expect

"How do you avoid overflow in mid^n?"
"What's the monotonic predicate?"
"What if a decimal root were required?"
"Why not use pow?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview