Skip to content

005 — Pow(x, n)

Source

  • Original source: Classic divide-and-conquer exercise (fast exponentiation)
  • Platform: LeetCode — https://leetcode.com/problems/powx-n/
  • Topic: recursion (divide-and-conquer)
  • Difficulty: Medium
  • Pattern: divide-and-conquer — exponent অর্ধেক করে square করা (fast power)
  • Basic idea inherited from: concept.md-র fast power

1. Problem in simple words

একটা সংখ্যা x (float) আর একটা integer exponent n দেওয়া আছে। তোমার কাজ: x কে n-তম power-এ তোলা, মানে x^n বের করা। n ঋণাত্মকও হতে পারে — তখন x^n = 1 / x^(-n)। সরল গুণ (x কে n বার গুণ) চলবে, কিন্তু সেটা ধীর; চাই দ্রুত উপায়।

pow(2, 10)  -> 1024
pow(2, -2)  -> 0.25      (1 / 2^2)
pow(2.1, 3) -> 9.261
pow(3, 0)   -> 1

2. Which basic idea does this inherit from?

ভিত্তি হলো concept.md-র fast power — divide-and-conquer। সরল চিন্তায় x^n মানে x কে n বার গুণ (O(n))। কিন্তু x^n = (x^(n/2))^2 — অর্ধেক exponent একবার বের করে square করলেই হয়। এটা Power of Two-র halving idea-র বড় ভাই: সেখানে আমরা ভাগ করছিলাম, এখানে exponent অর্ধেক করে multiply করছি।

3. What is the hidden math or logic?

লুকানো math হলো exponent-এর দুটো নিয়ম: x^(2k) = (x^k)^2 আর x^(2k+1) = (x^k)^2 · x। অর্থাৎ exponent জোড় হলে অর্ধেকের ফল square করো; বিজোড় হলে square করে একবার বাড়তি x গুণ করো। ঋণাত্মক exponent-এর জন্য: x^n = 1 / x^(-n)। এই recurrence-ই exponent-কে প্রতি ধাপে অর্ধেক করে, log n ধাপে নামায়।

4. Which data structure is needed?

কোনো data structure লাগে না — শুধু float arithmetic আর recursion-এর জন্য call stack। গুরুত্বপূর্ণ হলো অর্ধেকের ফলটা একটা variable-এ ধরে রাখা, যাতে দুবার compute না হয়।

5. Why this data structure fits

এখানে কিছু জমানোর দরকার নেই, শুধু একটা মান বারবার square করতে হয়। অর্ধেক exponent-এর ফল half variable-এ একবার রেখে half * half করাই মূল চাল — এই reuse-ই D&C-র combine step। যদি power(x, n//2) দুবার আলাদা call করতে, তাহলে আবার O(n) হয়ে যেত; একবার compute করে variable-এ রাখাই log n নিশ্চিত করে।

6. Real-life analogy

ভাবো তোমাকে এক টুকরো দড়ি 1024 গুণ লম্বা বানাতে হবে। এক হাত করে জোড়া না লাগিয়ে, তুমি দড়িটা একবার দ্বিগুণ করো (2x), সেটাকে আবার দ্বিগুণ (4x), আবার (8x)... মাত্র 10 বার দ্বিগুণ করলেই 1024x। প্রতিবার আগের ফলটাকেই square/double করছ — তাই অল্প কয়েক ধাপেই বিশাল power।

7. Visual explanation

প্রতি call exponent অর্ধেক করে — single chain, গভীরতা log n; ফেরত পথে square হয়:

power(2, 10)
   └ half = power(2, 5)
        └ half = power(2, 2)
             └ half = power(2, 1)
                  └ half = power(2, 0) = 1   (base case)
                  └ 1*1*2 = 2        (n=1 বিজোড়)
             └ 2*2 = 4               (n=2 জোড়)
        └ 4*4*2 = 32                 (n=5 বিজোড়)
   └ 32*32 = 1024                    (n=10 জোড়)

exponent 10-এর জন্য মাত্র ~4 level — O(log n)।

8. Example input and output

Input : x = 2,   n = 10  -> Output: 1024
Input : x = 2,   n = -2  -> Output: 0.25
Input : x = 2.1, n = 3   -> Output: 9.261

Edge case 1 (exponent 0): x = 5, n = 0 -> Output: 1
Edge case 2 (ঋণাত্মক): x = 2, n = -3 -> Output: 0.125

9. Brute force thinking

প্রথম সরল চিন্তা: একটা accumulator 1 থেকে শুরু করে x কে n বার গুণ করো (ঋণাত্মক হলে শেষে উল্টে দাও)।

result = 1
for i in range(abs(n)):
    result = result * x
return result if n >= 0 else 1 / result

10. Why brute force is slow

এই loop O(n) — exponent বড় হলে (যেমন n = 2^31) এটা বিলিয়ন বার গুণ করবে, timeout। মূল অপচয়: একই উপ-গুণফল বারবার আলাদা করে বানানো, অথচ x^n কে অর্ধেক exponent-এর square হিসেবে লিখলে প্রতি ধাপে কাজ অর্ধেক হয়ে O(log n)-এ নেমে আসত।

11. Key observation

মূল observation: x^n = (x^(n/2))^2 (জোড়), আর বিজোড় হলে একবার বাড়তি x। অর্থাৎ exponent অর্ধেক করতে করতে 0-এ পৌঁছানো যায়, প্রতি ধাপে শুধু একটা square (+ হয়তো এক গুণ)। n বার নয়, log n বার কাজ।

12. Optimized intuition

প্রথমে ঋণাত্মক exponent সামলাও: n < 0 হলে 1 / power(x, -n)। তারপর base case n == 0 → 1। নাহলে half = power(x, n // 2) একবার compute করে রাখো; n জোড় হলে half * half, বিজোড় হলে half * half * x। half একবারই বের করা বলে গভীরতা log n, time O(log n)। এটাই concept.md-র fast power-এর পূর্ণ রূপ।

13. Thinking tweak

মোচড়: "x কে n বার গুণ করব" ভাবার বদলে ভাবো "অর্ধেক power একবার বের করে square করব।" এই একটা square-ই প্রতি ধাপে কাজ অর্ধেক করে দেয় — linear থেকে logarithmic-এ লাফ। মূল শৃঙ্খলা: অর্ধেকের ফল একবারই compute করা (variable-এ রাখা)।

14. Step-by-step dry run

my_pow(2, 5):

  1. n = 5 > 0, n != 0 → half = my_pow(2, 2)।
  2. my_pow(2, 2): half = my_pow(2, 1)।
  3. my_pow(2, 1): half = my_pow(2, 0) = 1 (base)। n=1 বিজোড় → 1*1*2 = 2।
  4. ফিরে my_pow(2, 2): n=2 জোড় → 2*2 = 4।
  5. ফিরে my_pow(2, 5): n=5 বিজোড় → 4*4*2 = 32। উত্তর 32।

15. Python solution

def my_pow(x, n):
    if n < 0:                      # ঋণাত্মক exponent: উল্টে দাও
        return 1 / my_pow(x, -n)
    if n == 0:                     # base case: x^0 = 1
        return 1.0
    half = my_pow(x, n // 2)       # অর্ধেক একবারই compute করো
    if n % 2 == 0:
        return half * half         # জোড়: square
    return half * half * x         # বিজোড়: square + একবার বাড়তি x

# ---- tests (float, তাই tolerance দিয়ে তুলনা) ----
def close(a, b, eps=1e-9):
    return abs(a - b) < eps

assert close(my_pow(2, 10), 1024)
assert close(my_pow(2, -2), 0.25)         # ঋণাত্মক
assert close(my_pow(2.1, 3), 9.261)
assert close(my_pow(5, 0), 1.0)           # exponent 0
assert close(my_pow(2, -3), 0.125)
assert close(my_pow(3, 4), 81)
assert close(my_pow(2, 30), 1073741824)   # বড় exponent, তবু দ্রুত
print("সব test pass!")

16. Line-by-line code explanation

  • if n < 0: return 1 / my_pow(x, -n) — ঋণাত্মক power-কে ধনাত্মক করে নিয়ে শেষে reciprocal।
  • if n == 0: return 1.0 — base case; যেকোনো সংখ্যার 0-power হলো 1।
  • half = my_pow(x, n // 2) — অর্ধেক exponent একবার compute করে variable-এ রাখা (এটাই key)।
  • if n % 2 == 0: return half * half — exponent জোড়: শুধু square।
  • return half * half * x — exponent বিজোড়: square করে একবার বাড়তি x গুণ।

17. Output walkthrough

my_pow(2, 10): exponent 10→5→2→1→0, ফেরত পথে 1→2→4→32→1024। my_pow(2, -2) ভেতরে my_pow(2, 2)=4 বের করে 1/4 = 0.25 দেয়। my_pow(2.1, 3) দেয় 9.261। বড় my_pow(2, 30) মাত্র ~5 level-এ 1073741824। সব tolerance-সহ মিলছে, তারপর print: সব test pass!।

18. Time complexity

O(log n) — প্রতি call exponent অর্ধেক হয়, তাই মোট ~log₂|n| ধাপ, প্রতিটায় constant কাজ।

19. Space complexity

O(log n) — call stack-এর গভীরতা log n; কোনো extra collection নেই।

20. Common mistakes

  • অর্ধেকের ফল variable-এ না রেখে my_pow(x, n//2) * my_pow(x, n//2) লেখা — তখন কাজ দ্বিগুণ হয়ে আবার O(n)।
  • ঋণাত্মক exponent ভুলে যাওয়া — n < 0 case না থাকলে ভুল/infinite।
  • integer int overflow (অন্য ভাষায়); Python-এ সমস্যা নেই, তবে float precision-এ tolerance দিয়ে তুলনা করো।
  • n // 2 বিজোড় exponent-এ floor করে — তাই বিজোড় হলে বাড়তি x গুণ করতে ভুলো না।

21. Which basic problem this inherits from

ভিত্তি: Power of Two (এই tracker-এর #4)-এর halving + concept.md-র fast power। ../concept.md-এর "Divide-and-conquer: fast power" আর ../patterns.md-এর Pattern 2 দেখো — ওটাই এই note-এর তাত্ত্বিক ভিত।

22. Similar harder problems

23. Pattern learned

Divide-and-conquer fast power: x^n = (x^(n/2))^2 (বিজোড় হলে · x); অর্ধেক একবার compute করে square — O(n) থেকে O(log n)। যেকোনো associative operation-এ (গুণ, matrix product) এই halving exponentiation খাটে।

24. Final summary

ভবিষ্যতের আমাকে: "Pow = অর্ধেক exponent একবার বের করো, square করো; বিজোড় হলে একবার বাড়তি x, ঋণাত্মক হলে reciprocal।" যখনই কোনো কিছু n বার পুনরাবৃত্তি করতে হবে আর operation-টা associative — এই fast-power halving trick মনে করবে।

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