Pow X N¶

Problem¶

Implement pow(x, n), which calculates x raised to the power n (i.e., x^n). Handle negative exponents.

Approach¶

Fast exponentiation (exponentiation by squaring). If n is even, pow(x, n) = pow(x*x, n//2). If n is odd, pow(x, n) = x * pow(x, n-1). For negative n, compute pow(1/x, -n).

When to Use¶

Any "repeated operation" that can be halved — exponentiation, matrix power, modular arithmetic. Foundation of divide-and-conquer thinking.

Complexity¶


Time	`O(log n)`
Space	`O(log n) — recursion stack`

Implementation¶

SolutionTestsChallenge

pow_x_n ¶

Pow(x, n) — compute x raised to the power n using fast exponentiation.

Problem

Implement pow(x, n), which calculates x raised to the power n (i.e., x^n). Handle negative exponents.

Approach

Fast exponentiation (exponentiation by squaring). If n is even, pow(x, n) = pow(x*x, n//2). If n is odd, pow(x, n) = x * pow(x, n-1). For negative n, compute pow(1/x, -n).

When to use

Any "repeated operation" that can be halved — exponentiation, matrix power, modular arithmetic. Foundation of divide-and-conquer thinking.

Complexity

Time: O(log n) Space: O(log n) — recursion stack

my_pow ¶

my_pow(x: float, n: int) -> float

Compute x raised to the power n via fast exponentiation.

my_pow(2.0, 10) 1024.0 my_pow(2.0, -2) 0.25 my_pow(0.0, 0) 1.0

Source code in src/algo/recursion/pow_x_n.py

def my_pow(x: float, n: int) -> float:
    """Compute x raised to the power n via fast exponentiation.

    >>> my_pow(2.0, 10)
    1024.0
    >>> my_pow(2.0, -2)
    0.25
    >>> my_pow(0.0, 0)
    1.0
    """
    if n < 0:
        return my_pow(1.0 / x, -n)
    if n == 0:
        return 1.0
    if n % 2 == 0:
        return my_pow(x * x, n // 2)
    return x * my_pow(x, n - 1)

tests/recursion/test_pow_x_n.py

"""Tests for the pow(x, n) problem."""

import math

import pytest
from hypothesis import given
from hypothesis import strategies as st

from algo.recursion.pow_x_n import my_pow


class TestMyPow:
    def test_positive_exponent(self) -> None:
        assert my_pow(2.0, 10) == pytest.approx(1024.0)

    def test_negative_exponent(self) -> None:
        assert my_pow(2.0, -2) == pytest.approx(0.25)

    def test_zero_exponent(self) -> None:
        assert my_pow(5.0, 0) == pytest.approx(1.0)

    def test_exponent_one(self) -> None:
        assert my_pow(3.0, 1) == pytest.approx(3.0)

    def test_fractional_base(self) -> None:
        assert my_pow(0.5, 3) == pytest.approx(0.125)

    def test_negative_base_odd_exponent(self) -> None:
        assert my_pow(-2.0, 3) == pytest.approx(-8.0)

    @given(
        x=st.floats(
            min_value=0.1, max_value=10.0, allow_nan=False, allow_infinity=False
        ),
        n=st.integers(min_value=0, max_value=20),
    )
    def test_matches_builtin_pow(self, x: float, n: int) -> None:
        result = my_pow(x, n)
        expected = math.pow(x, n)
        assert result == pytest.approx(expected, rel=1e-9)

Implement it yourself

Run: just challenge recursion pow_x_n

Then implement the functions to make all tests pass. Use just study recursion for watch mode.

Reveal Solution

pow_x_n ¶

Pow(x, n) — compute x raised to the power n using fast exponentiation.

Problem

Implement pow(x, n), which calculates x raised to the power n (i.e., x^n). Handle negative exponents.

Approach

Fast exponentiation (exponentiation by squaring). If n is even, pow(x, n) = pow(x*x, n//2). If n is odd, pow(x, n) = x * pow(x, n-1). For negative n, compute pow(1/x, -n).

When to use

Any "repeated operation" that can be halved — exponentiation, matrix power, modular arithmetic. Foundation of divide-and-conquer thinking.

Complexity

Time: O(log n) Space: O(log n) — recursion stack

my_pow ¶

my_pow(x: float, n: int) -> float

Compute x raised to the power n via fast exponentiation.

my_pow(2.0, 10) 1024.0 my_pow(2.0, -2) 0.25 my_pow(0.0, 0) 1.0

Source code in src/algo/recursion/pow_x_n.py

def my_pow(x: float, n: int) -> float:
    """Compute x raised to the power n via fast exponentiation.

    >>> my_pow(2.0, 10)
    1024.0
    >>> my_pow(2.0, -2)
    0.25
    >>> my_pow(0.0, 0)
    1.0
    """
    if n < 0:
        return my_pow(1.0 / x, -n)
    if n == 0:
        return 1.0
    if n % 2 == 0:
        return my_pow(x * x, n // 2)
    return x * my_pow(x, n - 1)