Why it works
- 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.
- 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.
- 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 ↗