binary exponentiation – Quinsh's Programming Record

Difficulty: medium
Topics: math, recursion

Implement pow(x, n), which calculates x raised to the power n

Example 1:
Input: x = 2.00000, n = 10
Output: 1024.00000

Example 2:
Input: x = 2.10000, n = 3
Output: 9.26100

Example 3:
Input: x = 2.00000, n = -2
Output: 0.25000

Solution

O(n) approach would be just multiplying x n times:

$Pow(x,n)=x*x*x\dotsm \Large$

O(logn) approach is using an algorithm called “binary exponentiation“. This requires understanding that x^n can be decomposed in 2 ways:

if n is even:

$x^{n} = {x}^{\frac{n}{2}}*{x}^{\frac{n}{2}} \Large$

if n is odd:

$x^{n} = x * x^{n-1} = x * {x}^{\frac{n-1}{2}} * {x}^{\frac{n-1}{2}} \Large$

This can be handled recursively. x^n is decomposed into expressions with smaller ‘n’s until n becomes 0. When n becomes 0, we return 1.

class Solution {
public:
    double binaryExp(double x, long long n) {
        if (n == 0) return 1;
       
        // Handle case where, n < 0.
        if (n < 0) return 1.0 / binaryExp(x, -1 * n);
       
        // Perform Binary Exponentiation.
        double rec = binaryExp(x, n / 2);
        if (n % 2 == 1) return x * rec * rec;
        else return rec * rec;
    }

    double myPow(double x, int n) {
        return binaryExp(x, (long long) n);
    }
};

Tag: binary exponentiation

50. Pow(x,n) – Solution

Solution