Problem link ও উৎস
- **Original source:** LeetCode — Pow(x, n)
- **Platform:** LeetCode —
- **Topic:** Math-based programming fundamentals → Level 2: Modular Arithmetic
- **Difficulty:** Medium
- **Pattern:** binary exponentiation (negative exponent twist)
- **Basic idea inherited from:** 029 — Modular Exponentiation (square-and-multiply)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা base `x` আর একটা integer exponent `n` দেওয়া। বের করতে হবে `x^n`। দুটো ভ্যারিয়েন্ট দেখব:
- **Float version (LeetCode Pow):** `x` একটা real সংখ্যা (যেমন 2.0), `n` যেকোনো integer — **negative হতে পারে** (`x^(-n) = 1 / x^n`)।
- **Mod version:** `x^n % m`, যেখানে `n` negative হলে inverse দিয়ে সামলাতে হয় (Fermat, `m` prime ধরে)।
মূল দাবি একই: `n` যত বড়ই হোক, `O(log n)`-তে উত্তর।
### Input ও output {#6-example-input-and-output}
```text
Float Pow(x, n):
x n -> x^n
------------------------------
2.0 10 -> 1024.0
2.0 -2 -> 0.25 (1 / 4)
2.0 0 -> 1.0
0.5 3 -> 0.125
3.0 -3 -> 0.037037... (1 / 27)
Mod power (m prime = 7):
x n m -> x^n % m
------------------------------
3 13 7 -> 3 (029-এর মতো, n positive)
3 -1 7 -> 5 inverse(3) mod 7 = 5
2 -2 7 -> 2 inverse(4) = 2 (4×2=8≡1)
```
edge case: `n = 0` → সবসময় 1 (float-এ 1.0); negative exponent-এ float চাই reciprocal, mod চাই inverse — দুটো ভিন্ন জিনিস।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা **জুম বা magnify**। `x = 2` মানে প্রতিবার ছবি দ্বিগুণ বড়। `x^3` = তিনবার দ্বিগুণ = 8 গুণ বড়।
এখন **negative** exponent? `x^(-3)` = তিনবার দ্বিগুণ ছোট = 1/8 — মানে উল্টো দিকে zoom out। তাই negative exponent মানে "একই কাজ, কিন্তু উল্টো দিক" — আগে 8 বের করি, তারপর উল্টে 1/8 করি।
আর কাগজ-ভাঁজের চালাকি (029-এর) এখানেও: 16 বার zoom পেতে 16 বার নয়, 4 বার দ্বিগুণ-করা (square) যথেষ্ট — প্রতিবার আগেরটা square হয়ে exponent দ্বিগুণ।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
সরাসরি **029 — Modular Exponentiation** থেকে। 029-এর while-loop (bit 1 হলে multiply, সবসময় square, `n >>= 1`) এখানে হুবহু — শুধু দুটো জিনিস যোগ:
- mod তুলে দিলে (বা না নিলে) float-এ একই loop কাজ করে।
- negative exponent-এ আগে sign সামলে, শেষে reciprocal/inverse।
মানে engine একই, চারপাশে দুটো wrapper। আর inverse-এর ধারণাটা 032 (Fermat inverse)-এর দিকে সেতু — তাই এই দুটো note পাশাপাশি পড়লে ভালো।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
ভিত সেই **binary exponentiation (square-and-multiply)** — 029-এর engine। নতুন যোগ দুটো:
1. **Negative exponent:** `x^(-n) = 1 / (x^n)`। তাই `n < 0` হলে `n`-কে positive বানিয়ে power বের করো, তারপর reciprocal নাও। float-এ `1 / result`; mod-এ result-এর **modular inverse**।
2. **Float base:** গণিত একই, শুধু integer-এর জায়গায় float গুণ; mod নেই।
মূল insight যা interview-তে বলতে হয়: naive `x` কে `n` বার গুণ = O(n); square-and-multiply = O(log n) — exponent binary-তে ভাঙার ফল।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সরল: `x` কে `|n|` বার গুণো; n negative হলে শেষে reciprocal।
```python
def my_pow_brute(x, n):
if n < 0:
x = 1 / x # negative -> base উল্টে দিই
n = -n
result = 1.0
for _ in range(n):
result *= x # |n| বার গুণ
return result
```
ঠিক উত্তর দেয়। সমস্যা একটাই — loop চলে `|n|` বার।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
loop ঘোরে `|n|` বার। LeetCode-এ `n` −2³¹ থেকে 2³¹−1 পর্যন্ত — মানে প্রায় 2 বিলিয়ন iteration হতে পারে। সেকেন্ডে 10⁸ ধরলেও 20+ সেকেন্ড — Time Limit Exceeded।
```text
n = 2^31 ≈ 2.1×10^9 হলে:
brute (O(n)): ~2.1 বিলিয়ন গুণ -> TLE
binary (O(log n)): ~31 বার গুণ -> ঝটপট
log2(2^31) = 31 -> 2 বিলিয়ন বনাম 31
```
মূল শিক্ষা: 029-এর মতোই — exponent এক করে না কমিয়ে প্রতি step-এ অর্ধেক করো।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
binary exponentiation, সঙ্গে negative-handling wrapper:
```python
def my_pow(x, n):
if n < 0:
x = 1 / x # x^(-n) = (1/x)^n
n = -n
result = 1.0
while n > 0:
if n & 1: # last bit 1 হলে গুণ
result *= x
x *= x # square
n >>= 1 # অর্ধেক
return result
```
লক্ষ করো একটা সুন্দর চালাকি: negative হলে base-কে উল্টে (`1/x`) তারপর exponent positive ধরে চালালেই reciprocal আপনি এসে যায় — আলাদা করে শেষে ভাগ করতে হয় না।
mod version-এ একই, শুধু `1/x`-এর জায়গায় modular inverse:
```python
def power_mod_signed(x, n, m): # m prime ধরে (Fermat inverse)
if n < 0:
x = pow(x, m - 2, m) # x^(-1) mod m = x^(m-2)
n = -n
return pow(x, n, m)
```
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!": **negative exponent-কে আলাদা ভয়ের জিনিস ভেবো না — base-কে একবার উল্টে (float-এ `1/x`, mod-এ inverse) তারপর positive exponent-এর জানা engine চালাও।** sign-টা শুরুতেই সামলে নিলে বাকি গল্প 029-এর হুবহু পুনরাবৃত্তি।
আর interview-তে এই এক লাইন গেঁথে রাখো: "naive O(n) গুণ, কিন্তু exponent binary-তে ভাঙলে O(log n) — square-and-multiply।" এই গল্পটাই তারা শুনতে চায়।
### ছবিতে বোঝা {#5-visual-explanation}
negative exponent-কে positive-এ ফেরানো:
```text
x^(-n) = 1 / (x^n)
x = 2.0, n = -10:
step 1: n < 0 -> positive করি: |n| = 10
step 2: 2^10 = 1024 (square-and-multiply দিয়ে)
step 3: reciprocal: 1 / 1024 = 0.0009765625
```
mod-জগতে negative exponent (m = 7, Fermat):
```text
x^(-n) % m = inverse(x^n) % m = (x^n)^(m-2) % m [m prime]
বা সমতুল্য: x^(-1) = x^(m-2), তাই
x^(-3) % 7 = (x^(m-2))^3 % 7 = (x^5)^3 % 7 [m=7 -> m-2=5]
```
square-and-multiply অংশ 029-এর ছবির মতোই — শুধু শেষে sign অনুযায়ী reciprocal/inverse।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`my_pow(2.0, -10)`:
```text
n < 0 -> x = 1/2.0 = 0.5, n = 10 (এখন (0.5)^10 চাই)
10 = 1010₂
```
| step | n (binary) | last bit | result | x (square হয়ে) |
| --- | --- | --- | --- | --- |
| শুরু | 1010 | — | 1.0 | 0.5 |
| 1 | 1010 | 0 | 1.0 | 0.25 |
| 2 | 101 | 1 | 1.0 × 0.25 = 0.25 | 0.0625 |
| 3 | 10 | 0 | 0.25 | 0.00390625 |
| 4 | 1 | 1 | 0.25 × 0.00390625 = 0.0009765625 | ... |
`n` এখন 0, থামল। উত্তর **0.0009765625** = 1/1024 ✓ (2^(-10) = 1/1024)।
লক্ষ করো 10 = 8 + 2, তাই bit 1 ছিল step 2 (2-এর ঘর) আর step 4 (8-এর ঘর)-এ — সেখানেই result-এ গুণ হলো।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def my_pow(x, n):
"""x^n (float), negative n সহ — binary exponentiation, O(log n)।"""
if n < 0:
x = 1 / x # x^(-n) = (1/x)^n
n = -n
result = 1.0
while n > 0:
if n & 1:
result *= x
x *= x
n >>= 1
return result
def power_mod_signed(x, n, m):
"""x^n % m, negative n সহ; m prime ধরে Fermat inverse।"""
x %= m
if n < 0:
x = pow(x, m - 2, m) # modular inverse of x
n = -n
return pow(x, n, m)
# --- Float Pow test (LeetCode ধাঁচ) ---
assert abs(my_pow(2.0, 10) - 1024.0) < 1e-9
assert abs(my_pow(2.0, -2) - 0.25) < 1e-9
assert abs(my_pow(2.0, 0) - 1.0) < 1e-9
assert abs(my_pow(0.5, 3) - 0.125) < 1e-9
# Python-এর built-in float power-এর সাথে মিল:
assert abs(my_pow(2.0, -10) - 2.0 ** -10) < 1e-12
assert abs(my_pow(3.0, 7) - 3.0 ** 7) < 1e-9
assert abs(my_pow(1.5, -5) - 1.5 ** -5) < 1e-12
# --- Mod power (m = 7 prime) test ---
assert power_mod_signed(3, 13, 7) == pow(3, 13, 7) # positive
assert power_mod_signed(3, -1, 7) == 5 # inverse(3)=5
assert (3 * power_mod_signed(3, -1, 7)) % 7 == 1 # যাচাই: x·x^(-1)=1
assert power_mod_signed(2, -2, 7) == 2 # inverse(4)=2
assert (4 * power_mod_signed(2, -2, 7)) % 7 == 1
print(my_pow(2.0, 10)) # 1024.0
print(my_pow(2.0, -2)) # 0.25
print(power_mod_signed(3, -1, 7))# 5
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
if n < 0:
x = 1 / x
n = -n
```
negative exponent হলে base-কে উল্টে দিই (`1/x`) আর exponent-কে positive করি। কারণ `x^(-n) = (1/x)^n` — এক চালেই reciprocal সামলে গেল।
```text
while n > 0:
if n & 1:
result *= x
x *= x
n >>= 1
```
এটা হুবহু 029-এর engine: last bit 1 হলে current `x` (= `x^(2^k)`) result-এ গুণো; সবসময় `x` square করো; `n` অর্ধেক করো। শুধু এখানে mod নেই, float গুণ।
```text
def power_mod_signed(x, n, m):
x %= m
if n < 0:
x = pow(x, m - 2, m)
n = -n
return pow(x, n, m)
```
mod version: negative হলে float-এর `1/x`-এর বদলে **modular inverse** `x^(m-2) mod m` (Fermat, m prime)। তারপর positive exponent-এ সাধারণ `pow(x, n, m)`।
`assert (3 * power_mod_signed(3, -1, 7)) % 7 == 1` লাইনগুলো inverse-এর সংজ্ঞা সরাসরি যাচাই করছে: `x · x^(-1) ≡ 1`। float-গুলো built-in `**`-এর সাথে মিলছে। সব ঠিক থাকলে শেষে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
1024.0
0.25
5
সব test pass!
```
প্রথম লাইন `my_pow(2.0, 10)` → 1024.0। দ্বিতীয় `my_pow(2.0, -2)` → 0.25 (1/4)। তৃতীয় `power_mod_signed(3, -1, 7)` → 5 (3-এর inverse mod 7, কারণ 3×5=15≡1)। আগের সব `assert` (built-in `**` আর inverse-যাচাই সহ) চুপচাপ pass — তারপর `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(log n)** — দুটো version-এই while-loop প্রতিবার `n` অর্ধেক করে (`n >>= 1`)। mod version-এ ভেতরের `pow(x, n, m)`-ও O(log n), আর inverse-এর `pow(x, m-2, m)` O(log m) — মোট O(log n + log m)। naive O(n)-এর তুলনায় আকাশ-পাতাল।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — শুধু `x`, `n`, `result` variable; কোনো list/array/recursion লাগছে না। (recursive `Pow` লিখলে stack O(log n) হতো।)
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
- **negative exponent ভুলে যাওয়া** — `n < 0` handle না করলে loop শুরুই হয় না (n>0 false), উত্তর ভুল 1। আগে sign সামলাও।
- **mod-এ `1/x` লেখা** — modular জগতে float reciprocal নেই; inverse লাগে (`x^(m-2)` যদি m prime)। mod-এ `1/x` লিখলে ভুল।
- **`n = -n` overflow (C++)** — C++-এ `n = INT_MIN` হলে `-n` overflow করে; `long long`-এ নাও বা সাবধানে handle করো। Python-এ এ সমস্যা নেই।
- **`x = 0`, `n < 0`** — `1/0` — division by zero। গণিতে অসংজ্ঞায়িত; প্রয়োজনে আলাদা handle।
- **float-এ exact compare** — `==` দিয়ে float মেলানো বিপজ্জনক (rounding); `abs(a - b) < 1e-9` দিয়ে তুলনা করো।
- **mod base আগে না নেওয়া** — `x %= m` আগে নিলে নিরাপদ; নাহলে inverse/power-এ বড় সংখ্যা।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Super Pow** (