LeetCode 50 Explained ⚡ | Fast Power Using Bit Manipulation (Java)

🚀 Problem Overview

In **LeetCode 50 (Pow(x, n))**, we’re asked to compute ( x^n ) efficiently — even when:

`n` is very large
`n` is negative
brute-force multiplication would be too slow

This problem is a classic test of **optimization and mathematical thinking**.

---

🧠 Algorithm & Approach (Fast Power / Binary Exponentiation)

In this video, I explain a *highly optimized iterative solution* using **binary exponentiation and bit manipulation**.

#### ✅ Key Ideas:

Convert `n` to a `long` to safely handle `Integer.MIN_VALUE`
If `n` is negative:

Invert the base → `x = 1 / x`
Make the power positive
Use *binary representation of `n`* to reduce operations

---

⚙️ How the Algorithm Works

While `pow greater than 0`:

If the *last bit is 1* (`pow & 1`), multiply `result` by `x`
Square the base (`x *= x`)
Right shift the power → divide by 2

This reduces the time complexity drastically compared to naive solutions.

---

⏱️ Complexity Analysis

*Time Complexity:*
( O(\log n) ) — only process each bit of `n`
*Space Complexity:*
( O(1) ) — fully in-place, no recursion, no extra memory

---

💡 Why This Solution Is Optimal

Handles negative powers safely
Avoids recursion (stack-safe)
Uses bit manipulation for maximum efficiency
Industry-standard approach used in real systems

---

📌 What You’ll Learn

Binary exponentiation explained intuitively
Bitwise operations in real problems
How to avoid overflow edge cases
Writing clean, interview-ready Java code

---

👍 Like, comment, and subscribe if this helped you
💬 Questions and improvements are always welcome

Follow me on my socials to connect and see more awesome stuff

📌 *GitHub:* [https://github.com/NganeEmmanue](https://github.com/NganeEmmanue)
💼 *LinkedIn:* [  / ngane-emmanuel-b25242150  ](  / ngane-emmanuel-b25242150  )
📸 *Instagram:* @nganeemmanuel