The Fast Climber

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L4
Asked in
Citadel

Problem

Return base raised to the integer power exp, computed without the ** operator or pow(), neither of which our math utility can call. Exponents may be negative and can reach the billions on a hot path.

Some routes up the mountain are faster than others.

Example 1

Input:

base = 2, exp = 10

Output:

1024

Example 2

Input:

base = 2, exp = -2

Output:

0.25

Worked solution and explanation

This is binary exponentiation in a math-utility costume, and what separates candidates is not the squaring: it is the sign of exp. Most people write result = 1.0 and then for _ in range(exp): result *= base, which passes every positive case. But range(-2) is empty, so power_fast(2.0, -2) quietly hands back 1.0 instead of 0.25, and every negative exponent returns 1.0. The same loop also does a billion multiplications when the exponent is a billion, which the hot path will not survive.

Build it in three moves

Step 1: Fold the sign away first

A negative exponent is just a positive one on the reciprocal: x^(-n) = (1/x)^n. Swap base for 1.0 / base and negate exp before anything else, and the rest of the function only ever sees a non-negative exponent. Doing it up front means one division total, not one per step.

Step 2: Walk the bits of exp

Keep a current value that starts at base and is squared every iteration, so it holds base^1, base^2, base^4, and so on. Each time the low bit of exp is set (exp % 2 == 1), that power belongs in the answer, so multiply it into result. Halve exp with //= 2 and repeat until it hits zero.

Step 3: Let zero and sign parity fall out

Starting result at 1.0 makes exp == 0 free: the loop never runs and the identity comes back. A negative base needs no special case either, because squaring makes even powers positive and the odd bit multiplies one negative factor back in, so (-2.0)^3 lands on -8.0.

Square-and-halve with the sign folded in
def power_fast(base: float, exp: int) -> float:
    if exp < 0:
        base = 1.0 / base
        exp = -exp
    result = 1.0
    current = base
    while exp > 0:
        if exp % 2 == 1:
            result *= current
        current *= current
        exp //= 2
    return result

One reciprocal up front, then about log2(|exp|) squarings.

One multiply per unit
for _ in range(exp) does |exp| multiplications and returns 1.0 for every negative exp because the range is empty. At an exponent of a billion it runs for a minute.
Square and halve
The while exp > 0 loop does two multiplications per bit of exp, so a billion takes about 30 iterations, and the reciprocal swap covers negative exponents before the loop starts.

Common follow-up questions