DSA interview question

Pow(x, n) with Iterative Binary Exponentiation

Easy · Algorithms · Topics: math, divide and conquer

The problem

A physics engine evaluates x^n inside a hot loop millions of times per frame, so it needs the fastest, allocation-free version: no recursion. Binary exponentiation reads the bits of n from least to most significant while repeatedly squaring x: after k squarings, x holds x^(2^k), and it's multiplied into the result exactly when bit k of n is 1. Negative exponents use 1/x with a 64-bit exponent so n = INT_MIN is safe.

Example: x = 3, n = 5 (101 in binary) → 3^4 · 3^1 = 243.

Function signature

double myPow(double x, int n);

Test cases

Input `(x, n)`	Output	Explanation
`(2.00000, 10)`	`1024.00000`	10 = 1010: 2⁸ · 2²
`(2.10000, 3)`	`9.26100`
`(2.00000, -2)`	`0.25000`
`(3.00000, 5)`	`243.00000`	5 = 101: 3⁴ · 3¹
`(-1.00000, -2147483648)`	`1.00000`	Even exponent; negating INT_MIN needs 64 bits
`(0.00000, 5)`	`0.00000`

(Confirm: x ≠ 0 when n < 0; answers within 10⁻⁵ are accepted; O(log |n|) time and O(1) space.)

How interviewers phrase it

"Implement pow(x, n)" (LeetCode 50), followed by "can you do it iteratively in O(1) space?"
The modular version (a^b) mod m is the backbone of many number-theory problems.

Clarifying questions to ask

Can n be negative, including INT_MIN?
Is recursion allowed? (This version avoids it.)
Do you also want the modular variant?

Follow-ups to expect

"Explain it via the binary representation."
"Why use a 64-bit exponent?"
"Modular version?"
"How many multiplications?"
"Recursive vs iterative?"

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