DSA interview question

Pow(x, n) Using Recursion

Easy · Algorithms · Topics: recursion, math, divide and conquer

The problem

A finance calculator needs x^n for compound growth, where x is a double and n can be any 32-bit integer, including negatives (discounting) and huge values. Multiplying x by itself n times takes O(n), which is far too slow for n = 2 billion. The recursive divide-and-conquer idea: compute x^(n/2) once, square it, and multiply by one more x if n is odd. That halves n on every call, so the depth is only about 31.

Example: x = 2.0, n = 10 → 1024.0; x = 2.0, n = -2 → 0.25.

Function signature

double myPow(double x, int n);

Test cases

Input `(x, n)`	Output	Explanation
`(2.00000, 10)`	`1024.00000`
`(2.10000, 3)`	`9.26100`
`(2.00000, -2)`	`0.25000`	1 / 2²
`(1.00000, -2147483648)`	`1.00000`	n = INT_MIN, whose negation overflows int
`(-2.00000, 3)`	`-8.00000`	An odd power keeps the sign

(Confirm: x is not 0 when n is negative; the result fits in a double; answers within 10⁻⁵ are accepted.)

How interviewers phrase it

"Implement pow(x, n), which calculates x raised to the power n" (LeetCode 50), expected in O(log n).
In the recursion section, the focus is the halving recurrence and its depth.

Clarifying questions to ask

Can n be negative? Can it be INT_MIN?
Can x be 0 with a negative n? (Assume not.)
What precision is expected?

Follow-ups to expect

"Why not recurse twice on n/2?"
"How do you handle negative n?"
"What's the recursion depth?"
"Iterative version?"
"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