LeetCode: 50. Pow(x, n)

50. Pow(x, n)

50. Pow(x, n)

Summary

Calculate x^n without using built-in operators such as x ** n in Python.

Approach

Convert n to binary. For each bit from right to left, calculate the corresponding power of x.

• the first bit: x
• the second bit: x^2
• the third bit: (x^2)^2
• ...

If the bit at the i-th step is 1, multiply the current power into the answer.

Function

Initialization:

• flag = -1 if n < 0, otherwise 1
• n = abs(n)
• pow = x
• ans = 1

While n > 0:

• extract the lowest bit with n & 1
• if the lowest bit is 1, do ans *= pow
• square the current power with pow *= pow
• right shift n with n >>= 1

Complexity

Time complexity: O(log N), because we process one bit of n at a time. Space complexity: O(1).