The idea
Divide and conquer breaks a problem into smaller copies of itself, solves them recursively, and merges the results. If merging takes O(n), the total is O(n log n), as in merge sort.
Sometimes only one half is needed. Binary exponentiation computes aᵇ from a^(b/2), so it takes O(log b) multiplications instead of b.
It also counts things that cross the middle: inversions during a merge, or the best subarray that spans both halves.
Sample problem
50. Pow(x, n) ↗ Medium
Implement pow(x, n): x raised to the integer power n, where n can be negative and as large as 2³¹ in size.
x = 2, n = 10 output = 1024
Why the solution works
Multiplying x by itself n times is too slow when n is two billion. Split the problem instead: xⁿ = (x^(n/2))², times one more x when n is odd.
The half is computed once and squared, so each call halves the exponent and the depth is only log₂ n. Computing the half twice would undo the saving.
A negative exponent is the reciprocal of the positive one. The exponent is widened to long long first because −INT_MIN does not fit in an int.
Complexity: O(log n) time and recursion depth.
Watch out
- Call the recursion once and reuse the result. Writing
power(a, b/2) * power(a, b/2)brings the cost back to O(b). - Reduce modulo before multiplying so the product fits in
long long. - The combine step must handle answers that cross the midpoint, not only those inside one half.