030 — Fast Power¶

029-এ binary exponentiation-এর engine বানিয়েছ। এই note-এ সেই engine-কেই দুই নতুন রূপে দেখব: একটা LeetCode-এর classic Pow(x, n) — float base, negative exponent; আরেকটা mod-জগতে negative exponent (যেখানে inverse লাগে)। interview-তে এই "O(n) থেকে O(log n)" গল্পটাই interviewer শুনতে চায়।

Source¶

Original source: LeetCode — Pow(x, n)
Platform: LeetCode — https://leetcode.com/problems/powx-n/
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)

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)-তে উত্তর।

2. What is the math idea?¶

ভিত সেই binary exponentiation (square-and-multiply) — 029-এর engine। নতুন যোগ দুটো:

Negative exponent: x^(-n) = 1 / (x^n)। তাই n < 0 হলে n-কে positive বানিয়ে power বের করো, তারপর reciprocal নাও। float-এ 1 / result; mod-এ result-এর modular inverse।
Float base: গণিত একই, শুধু integer-এর জায়গায় float গুণ; mod নেই।

মূল insight যা interview-তে বলতে হয়: naive x কে n বার গুণ = O(n); square-and-multiply = O(log n) — exponent binary-তে ভাঙার ফল।

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 পাশাপাশি পড়লে ভালো।

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 দ্বিগুণ।

5. Visual explanation¶

negative exponent-কে positive-এ ফেরানো:

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):

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।

6. Example input and output¶

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 — দুটো ভিন্ন জিনিস।

7. Brute force thinking¶

সরল: x কে |n| বার গুণো; n negative হলে শেষে reciprocal।

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।

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:

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:

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।" এই গল্পটাই তারা শুনতে চায়।

11. Step-by-step dry run¶

my_pow(2.0, -10):

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-এ গুণ হলো।

12. Python solution¶

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¶

    if n < 0:
        x = 1 / x
        n = -n

negative exponent হলে base-কে উল্টে দিই (1/x) আর exponent-কে positive করি। কারণ x^(-n) = (1/x)^n — এক চালেই reciprocal সামলে গেল।

    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 গুণ।

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!।

14. Output walkthrough¶

চালালে যা ছাপবে:

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!।

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-এ বড় সংখ্যা।

18. Harder problems that inherit this idea¶

LeetCode — Super Pow (https://leetcode.com/problems/super-pow/) — exponent নিজেই array হিসেবে বিশাল; এই fast power + mod-এর সম্প্রসারণ।
032 (Modular Inverse Basic) (https://cp-algorithms.com/algebra/module-inverse.html) — এখানকার negative-exponent-mod আসলে inverse; 032-এ পুরো গল্প।
CSES — Exponentiation II (https://cses.fi/problemset/task/1712) — tower power a^(b^c), Fermat-এ exponent mod (p−1) — fast power-এর গভীর প্রয়োগ।

19. Pattern learned¶

Fast power with sign handling — binary exponentiation-এর engine একই; negative exponent হলে base উল্টাও (float-এ 1/x, mod-এ inverse x^(m-2)) আর exponent positive করো। "O(n) → O(log n) via binary" — interview-র মূল গল্প।

20. Final summary¶

ভবিষ্যতের আমাকে এক লাইনে: "Fast power = 029-এর square-and-multiply; negative exponent এলে আগে base উল্টে (float 1/x, mod x^(m-2)) positive বানাও, তারপর জানা loop। 'O(n) থেকে O(log n)' গল্পটাই interviewer চায়।"

পরের ধাপ → 031 — Large Number Mod (বিশাল সংখ্যার mod digit-by-digit)। সম্পর্কিত → 029 — Modular Exponentiation, 032 — Modular Inverse Basic।

ফিরে দেখা: এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · এই note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" এমন দাবি করা হয়নি — বরং "common interview pattern" / "CP-তে নিত্য দরকারি" লেখা।