title: Pow(x, n)
slug: powx-n
difficulty: medium
leetcode_id: 50
leetcode_url: https://leetcode.com/problems/powx-n/
categories:
  - math
  - recursion
patterns:
  - slug: binary-search
    is_optimal: true

function_signature: "def my_pow(x: float, n: int) -> float:"

test_cases:
  visible:
    - input: { x: 2.0, n: 10 }
      expected: 1024.0
    - input: { x: 2.1, n: 3 }
      expected: 9.261
    - input: { x: 2.0, n: -2 }
      expected: 0.25
  hidden:
    - input: { x: 1.0, n: 0 }
      expected: 1.0
    - input: { x: 5.0, n: 0 }
      expected: 1.0
    - input: { x: 2.0, n: 1 }
      expected: 2.0
    - input: { x: 2.0, n: -1 }
      expected: 0.5
    - input: { x: 0.5, n: 2 }
      expected: 0.25

description: |
  Implement `pow(x, n)`, which calculates `x` raised to the power `n` (i.e., x<sup>n</sup>).

constraints: |
  - `-100.0 < x < 100.0`
  - `-2^31 <= n <= 2^31 - 1`
  - `n` is an integer
  - Either `x` is not zero or `n > 0`
  - `-10^4 <= x^n <= 10^4`

examples:
  - input: "x = 2.00000, n = 10"
    output: "1024.00000"
    explanation: "2^10 = 1024"
  - input: "x = 2.10000, n = 3"
    output: "9.26100"
    explanation: "2.1^3 = 2.1 × 2.1 × 2.1 = 9.261"
  - input: "x = 2.00000, n = -2"
    output: "0.25000"
    explanation: "2^(-2) = 1/2^2 = 1/4 = 0.25"

explanation:
  intuition: |
    Imagine you need to calculate 2<sup>10</sup>. The naive approach would multiply 2 by itself 10 times, but there's a much faster way.

    Notice that 2<sup>10</sup> = 2<sup>5</sup> × 2<sup>5</sup>. We only need to calculate 2<sup>5</sup> once and square it! Similarly, 2<sup>5</sup> = 2<sup>2</sup> × 2<sup>2</sup> × 2. This pattern of **halving the exponent** at each step is the key insight.

    Think of it like this: instead of taking `n` steps to reach your answer, you can "teleport" by repeatedly squaring. Each squaring operation effectively doubles the exponent you've computed so far. This transforms an O(n) problem into O(log n).

    For negative exponents, remember that x<sup>-n</sup> = 1/x<sup>n</sup>. We can convert the problem to a positive exponent and take the reciprocal at the end.

    This technique is called **Binary Exponentiation** (or "exponentiation by squaring") because we're essentially using the binary representation of `n` to decide when to multiply.

  approach: |
    We solve this using **Binary Exponentiation (Iterative)**:

    **Step 1: Handle negative exponents**

    - If `n` is negative, convert to positive: set `n = -n` and `x = 1/x`
    - This transforms x<sup>-n</sup> into (1/x)<sup>n</sup>
    - Use a long integer for `n` to handle the edge case where `n = -2^31` (converting to positive would overflow a 32-bit int)

    &nbsp;

    **Step 2: Initialise variables**

    - `result`: Set to `1.0` — this accumulates our answer
    - `current_product`: Set to `x` — this tracks x<sup>2^k</sup> as we iterate

    &nbsp;

    **Step 3: Iterate while n > 0**

    - Check if the current bit of `n` is set (i.e., `n % 2 == 1` or `n & 1`)
    - If yes, multiply `result` by `current_product`
    - Square `current_product` to move to the next power of 2
    - Halve `n` (integer division by 2 or right shift)

    &nbsp;

    **Step 4: Return the result**

    - After processing all bits of `n`, return `result`

    &nbsp;

    The key insight is that any integer `n` can be expressed as a sum of powers of 2 (its binary representation). For example, 13 = 8 + 4 + 1 = 2<sup>3</sup> + 2<sup>2</sup> + 2<sup>0</sup>. So x<sup>13</sup> = x<sup>8</sup> × x<sup>4</sup> × x<sup>1</sup>. We compute each x<sup>2^k</sup> by repeated squaring and multiply them together when the corresponding bit is set.

  common_pitfalls:
    - title: Linear Time Multiplication
      description: |
        The naive approach of multiplying `x` by itself `n` times takes O(n) time:

        ```python
        result = 1
        for _ in range(n):
            result *= x
        ```

        With constraints allowing `n` up to 2<sup>31</sup> - 1 (about 2 billion), this approach will cause a **Time Limit Exceeded** error. Binary exponentiation reduces this to O(log n), which is approximately 31 operations for the worst case.
      wrong_approach: "Loop n times multiplying x"
      correct_approach: "Binary exponentiation with O(log n) multiplications"

    - title: Integer Overflow with Negative Exponent
      description: |
        When `n = -2^31` (the minimum 32-bit signed integer), converting it to positive by doing `n = -n` causes integer overflow because `2^31` cannot be represented in a signed 32-bit integer.

        For example, in many languages `-(-2147483648)` still equals `-2147483648` due to overflow.

        The fix is to use a 64-bit integer (long) for `n` after conversion, or handle this edge case separately.
      wrong_approach: "Convert n to positive using 32-bit int"
      correct_approach: "Use 64-bit integer or handle MIN_INT edge case"

    - title: Forgetting to Handle n = 0
      description: |
        By mathematical convention, x<sup>0</sup> = 1 for any non-zero `x`. Your algorithm should return `1.0` when `n = 0`.

        Initialising `result = 1.0` handles this automatically — if `n = 0`, the while loop never executes and we return `1.0`.

  key_takeaways:
    - "**Binary exponentiation pattern**: Reduce O(n) to O(log n) by repeatedly squaring and using the binary representation of the exponent"
    - "**Divide and conquer**: x<sup>n</sup> = x<sup>n/2</sup> × x<sup>n/2</sup> — solve half the problem and combine"
    - "**Handles negative exponents**: Transform x<sup>-n</sup> to (1/x)<sup>n</sup>"
    - "**Foundation for modular exponentiation**: This same technique is used in cryptography (RSA) to compute large powers under a modulus efficiently"

  time_complexity: "O(log n). We halve `n` at each iteration, so we perform at most log₂(n) multiplications."
  space_complexity: "O(1). We only use a constant number of variables (`result`, `current_product`, `n`)."

solutions:
  - approach_name: Binary Exponentiation (Iterative)
    is_optimal: true
    code: |
      def my_pow(x: float, n: int) -> float:
          # Handle negative exponent: x^(-n) = (1/x)^n
          if n < 0:
              x = 1 / x
              n = -n

          result = 1.0
          current_product = x  # Tracks x^(2^k)

          while n > 0:
              # If current bit is set, include this power in result
              if n % 2 == 1:
                  result *= current_product

              # Square to get next power: x^(2^k) -> x^(2^(k+1))
              current_product *= current_product

              # Move to next bit
              n //= 2

          return result
    explanation: |
      **Time Complexity:** O(log n) — We halve `n` at each iteration.

      **Space Complexity:** O(1) — Only constant extra space used.

      We iterate through the bits of `n`, squaring our base at each step. When a bit is set, we multiply that power into our result. This efficiently computes x<sup>n</sup> using the binary representation of `n`.

  - approach_name: Binary Exponentiation (Recursive)
    is_optimal: true
    code: |
      def my_pow(x: float, n: int) -> float:
          def helper(base: float, exp: int) -> float:
              # Base case: anything to the power 0 is 1
              if exp == 0:
                  return 1.0

              # Recursively compute half the power
              half = helper(base, exp // 2)

              # If exp is even: x^n = (x^(n/2))^2
              if exp % 2 == 0:
                  return half * half
              # If exp is odd: x^n = x * (x^(n/2))^2
              else:
                  return base * half * half

          # Handle negative exponent
          if n < 0:
              return helper(1 / x, -n)
          return helper(x, n)
    explanation: |
      **Time Complexity:** O(log n) — Recursion depth is log₂(n).

      **Space Complexity:** O(log n) — Due to recursion stack.

      This recursive approach expresses the same idea: x<sup>n</sup> = x<sup>n/2</sup> × x<sup>n/2</sup> (times x if n is odd). The iterative version is preferred for its O(1) space complexity.

  - approach_name: Brute Force
    is_optimal: false
    code: |
      def my_pow(x: float, n: int) -> float:
          # Handle negative exponent
          if n < 0:
              x = 1 / x
              n = -n

          result = 1.0
          # Multiply x by itself n times
          for _ in range(n):
              result *= x

          return result
    explanation: |
      **Time Complexity:** O(n) — Linear in the exponent value.

      **Space Complexity:** O(1) — Only constant extra space.

      This naive approach multiplies `x` by itself `n` times. While correct, it's far too slow when `n` can be up to 2^31. Included here to illustrate why binary exponentiation is necessary.
