# The Fast Climber

> Some routes up the mountain are faster than others.

Canonical URL: <https://datadriven.io/problems/the_fast_climber>

Domain: Python · Difficulty: medium · Seniority: L4

## Problem

Given a float base and an integer exponent (possibly negative), return base ** exp computed without using the ** operator or pow(). Use fast exponentiation (O(log |exp|)). Handle negative exponents by inverting at the end.

## Worked solution and explanation

### Why this problem exists in real interviews

This tests **exponentiation by squaring**, an O(log n) algorithm. It probes whether a candidate can optimize beyond naive repeated multiplication and handle negative exponents.

> **Trick to Solving**
>
> Use binary exponentiation: if the exponent is even, `x^n = (x^(n/2))^2`. If odd, `x^n = x * x^(n-1)`. This reduces the number of multiplications from O(n) to O(log n).

---

### Break down the requirements

#### Step 1: Handle negative exponents

Invert the base and negate the exponent: `x^(-n) = (1/x)^n`.

#### Step 2: Apply binary exponentiation

Square the base and halve the exponent on each step. Multiply into the result when the exponent is odd.

---

### The solution

**Binary exponentiation with negative handling**

```python
def fast_power(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
```

> **Time and Space Complexity**
>
> **Time:** O(log n) where n is the absolute value of the exponent.
> 
> **Space:** O(1). Only scalar variables.

> **Interviewers Watch For**
>
> Whether you handle edge cases: exponent of 0 (returns 1), base of 0 with negative exponent (division by zero).

> **Common Pitfall**
>
> Using naive repeated multiplication (O(n)). For large exponents like 10^9, this is far too slow.

---

## Common follow-up questions

- How is this used in modular arithmetic (e.g., RSA)? _(Tests modular exponentiation: `(base^exp) % mod` with the same squaring technique.)_
- What if the exponent is extremely large (10^18)? _(Tests that O(log n) handles this in about 60 iterations.)_
- How does Python's built-in `pow(base, exp, mod)` work internally? _(Tests knowledge that Python uses the same binary exponentiation with modular reduction.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_fast_climber)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.