Understanding Fast Power (Exponentiation by Squaring) - Pow(x, n) Step-by-Step - LeetCode 50

With Clear Diagrams + Recursive & Iterative Methods (C#) When solving Pow(x, n) in interviews (Google, Meta, etc.), a brute-force solution is NOT enough. The naive way: x * x * x * x * ... (n times) This takes O(n) time. But we can do better. We can solve it in: O(log n) Let's understand this deeply --- visually and line-by-line. 🧠 The Key Mathematical Insight If n is EVEN: x^n = (x^(n/2))² Example: 2^8 = (2^4)² = (16)² = 256 Why? Because: 2^8 = 2×2×2×2×2×2×2×2 = (2×2×2×2) × (2×2×2×2) = 2^4 × 2^4 If n is ODD: x^n = (x^((n-1)/2))² × x Example: 2^9 = 2 × 2^8 = 2 × (2^4)² We remove one x to make the exponent even. 🚀 Why This Is Faster Instead of reducing: n → n-1 → n-2 → ... We reduce: n → n/2 → n/4 → n/8 → ... So recursion depth becomes: O(log n) 📘 Recursive Method (C#) public class Solution { public double MyPow ( double x , int n ) { long N = n ; if ( N < 0 ) { x = 1 / x ; N = - N ; } return FastPow ( x , N ); } private double FastPow ( double x , long n ) { if ( n == 0 ) return 1 ; do