beingsde
Sign In
Back to all DSA patterns
Divide & Conquer / Math•Pattern: Divide & Conquer•Medium

Pow(x, n) — fast exponentiation

Problem Intuition & Objective

Compute x^n efficiently using binary exponentiation.

Time ComplexityO(log n)
Optimal
Space ComplexityO(log n) recursion / O(1) iterative
Memory Bounds
Optimal Algorithmic Approach

Binary exponentiation (exponentiation by squaring).

Core Invariants & Edge Cases

  • If n is even: x^n = (x²)^(n/2)
  • If n is odd: x^n = x × x^(n-1)
  • Handle negative n: x^(-n) = 1/x^n
Previous ProblemQuickSelect — find Kth smallest element in O(n) averageNext Problem Count inversions in array

System Design & Architecture Roadmap

Coding interviews are only 50% of the bar. Master High-Level Design, distributed systems, and Object-Oriented LLD.

60+ HLD QuestionsSharding, caching, and real-time distributed systems.27 LLD BlueprintsObject-oriented design patterns with class diagrams.SDE Quick ReferenceLatency numbers and database selection matrix.