কনটেন্টে যান

005 — Pow(x, n)

Problem link ও উৎস

  • 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

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

একটা সংখ্যা 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

Input ও 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

চেনা উদাহরণে বোঝা

ভাবো তোমাকে এক টুকরো দড়ি 1024 গুণ লম্বা বানাতে হবে। এক হাত করে জোড়া না লাগিয়ে, তুমি দড়িটা একবার দ্বিগুণ করো (2x), সেটাকে আবার দ্বিগুণ (4x), আবার (8x)... মাত্র 10 বার দ্বিগুণ করলেই 1024x। এই দড়ির উদাহরণে দৈর্ঘ্য double হচ্ছে। Exponentiation-এ ফল square হয়: x থেকে x², তারপর x⁴, তারপর x⁸। তাই exponent-এর binary digit ধরে অল্প কয়েক ধাপে power বের করা যায়।

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

ভিত্তি হলো 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 করছি।

ভেতরের যুক্তি

লুকানো 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 ধাপে নামায়।

কী দিয়ে তথ্য রাখব

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

এটি কেন উপযুক্ত

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

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

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

উদাহরণ
result = 1
for i in range(abs(n)):
    result = result * x
return result if n >= 0 else 1 / result

কোথায় বেশি কাজ হচ্ছে

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

যে বিষয়টি খেয়াল করতে হবে

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

আরও কম কাজে সমাধান

প্রথমে ঋণাত্মক 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-এর পূর্ণ রূপ।

ভাবনার পরিবর্তন

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

ছবিতে বোঝা

প্রতি 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)।

ছোট input-এ ধাপে ধাপে

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।

কোড ও ব্যাখ্যা

Python

Python
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!")

কোডের প্রতিটি অংশ

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

Output মিলিয়ে দেখা

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

খরচ ও সাধারণ ভুল

সময়

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

অতিরিক্ত জায়গা

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

যে ভুলগুলো এড়াতে হবে

  • অর্ধেকের ফল 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 গুণ করতে ভুলো না।

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

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

পরের অনুশীলন

কৌশলটি মনে রাখুন

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 খাটে।

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "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।