Pow(x, n)

Medium#50half the power

You get a number x and a whole number n, which may be negative. Work out x to the power n without a ready-made power function. Our example: x = 2, n = -13 — the answer is 1 / 8192 = 0.0001220703125.

50 Pow(x, n)Walkthrough · 1×

Example: raise 2 to the power -13: one over 2^13, and 2^13 from 2^6 squared times 2.

waiting on the call stackcurrent call, then the extra x of an odd nx^half, worked out by the call belowthe same half again, for free

n = -13 < 0: 2^-13 = 1 / 2^13

01/25
restart · back · play · step
Speed
1function myPow(x, n):
2 if n < 0:
3 return 1 / power(x, -n)
4 return power(x, n)
5
6function power(x, n):
7 if n == 0:
8 return 1
9 half = power(x, n / 2) // rounded down
10 if n is even:
11 return half * half
12 return half * half * x
state
x
2
n
-13
half
–
click a step to go back

← → step · space play/pause

Why it works

  1. x^n is x^(n/2) times itself, with one more x when n is odd: the problem for n turns into one problem for half of n.
  2. The half is worked out once and multiplied by itself, so each level costs one call and one or two multiplications, and n halves on every level down to 0.
  3. A negative n only flips the answer: x^-n = 1 / x^n.

Complexity

Time O(log n): n halves on every call, so there are about log n calls, each with at most two multiplications. Memory O(log n): the call stack holds one call per halving.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.