50. Pow(x,n)

Exponentiation by squaring / Binary Exponentiation

When we want to calculate $a^n$ , if both a and n are large, multiplying $a$ for $n$ times will be inefficient.

We can use the property: \(a^{b+c} = a^b · a^c\)

By expressing n in binary, we can split the computation into smaller powers of 2 and multiply only the necessary terms.

Examples

1. $x^8$

   From x, repeatedly square itself: \(x → x^2 → x^4 → x^8\)

   This takes only 3 squaring operations instead of 7 multiplications.

2. $x^{15}$

   During \(x → x^2 → x^4 → x^8\)

   we multiply all these intermediate powers: \(x * x^2 * x^4 * x^8 = x^{15}\)

How to know which powers to multiply?

Look at the binary representation of the exponent n: \(13=(1101)_2\) ​ From lowest to highest bit, if a bit is 1, multiply the corresponding power of x into the result:

• $(1101)_2$ → take $x^{2^0}$, $x^{2^2}$, $x^{2^3}$

• Skip bits with 0

Iterative Implementation Idea

We traverse bits of n from LSB to MSB:

1. Initialize result = 1
2. While n > 0:
   • If the lowest bit of n is 1 → multiply result by current x
   • Square x
   • Right shift n by 1

Solution

class Solution {
    public double myPow(double x, int n) {
        double res = 1;
        long N = n;
        if (N < 0) { // x^-n = (1/x)^n
            N = -N;
            x = 1 / x;
        }
        while (N != 0) { // Iterate over each bit of n from LSB to MSB
            if ((N & 1) == 1) { // Current bit is 1
                res *= x; // Multiply x into res
            }
            x *= x; // Square x
            N >>= 1; // Move to the next bit
        }
        return res;
    }
}

Time Complexity: O(log(|n|))
Space Complexity: O(1)