DSA Notes

Techniques

Divide & Conquer

Split the problem in half, solve each half, combine.

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.
Watch it run

Try your own input

Practise on LeetCode