004 — Power of Two¶

Problem link ও উৎস

Original source: Classic math / recursion exercise
Platform: LeetCode — https://leetcode.com/problems/power-of-two/
Topic: recursion (decrease-and-conquer, halving)
Difficulty: Easy
Pattern: decrease-and-conquer — বারবার 2 দিয়ে ভাগ
Basic idea inherited from: divisibility (math fundamentals)

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

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

একটা integer n দেওয়া আছে। বলতে হবে এটা 2-এর কোনো power কি না — মানে n == 2^k এমন কোনো k >= 0 আছে কি না (1, 2, 4, 8, 16, ...)। 1 হলো 2^0, তাই 1-ও power of two। তোমার কাজ: True বা False ফেরত দেওয়া।

উদাহরণ

1   -> True   (2^0)
16  -> True   (2^4)
3   -> False
0   -> False
-8  -> False

Input ও output¶

উদাহরণ

Input : n = 1   -> Output: True   (2^0)
Input : n = 16  -> Output: True   (2^4)
Input : n = 3   -> Output: False

Edge case 1 (শূন্য): n = 0   -> Output: False
Edge case 2 (ঋণাত্মক): n = -16 -> Output: False

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

একটা কাগজ ভাবো যেটা তুমি বারবার ঠিক অর্ধেক ভাঁজ করছ আর উল্টো দিকে ছিঁড়ছ। যদি প্রতিবার নিখুঁত দুই সমান টুকরো হয় আর শেষে ঠিক একটা টুকরোয় (1) পৌঁছাও, তাহলে শুরুর সংখ্যাটা 2-এর power ছিল। কোনো ধাপে যদি একটা টুকরো বেজোড় থেকে যায় (বিজোড় সংখ্যা), তাহলে না।

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

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

ভিত্তি হলো divisibility (math fundamentals)। একটা সংখ্যা 2-এর power মানে তাকে বারবার 2 দিয়ে ভাগ করতে করতে ঠিক 1-এ পৌঁছানো যায়, মাঝপথে কখনো বিজোড় ভাগশেষ না রেখে। তাই মূল কাজ হলো "2 দিয়ে নিঃশেষে ভাগ হয় কি না" — সেই check-টা recursively চালানো।

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

লুকানো logic: n = 2^k ⇔ n-এর একমাত্র prime factor হলো 2। অর্থাৎ 2 দিয়ে ভাগ করতে থাকলে কখনো বিজোড় ভাগশেষ আসবে না, আর শেষমেশ ঠিক 1-এ থামবে। তাই recurrence: is_pow(n) = is_pow(n / 2) যদি n জোড় হয়; base case n == 1 → True, আর n বিজোড় (>1) বা n <= 0 → False।

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

কোনো data structure লাগে না — শুধু integer arithmetic (% 2, // 2) আর recursion-এর জন্য call stack। এটা মূলত একটা math/divisibility problem।

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

এখানে কোনো collection জমাতে হয় না, শুধু একটা সংখ্যাকে বারবার অর্ধেক করতে হয়। Integer-এর modulo (% 2) আর floor division (// 2) দুটোই O(1), তাই প্রতিটা recursive call constant কাজ করে। কোনো array/map ছাড়াই কাজ চলে বলে এটা সবচেয়ে হালকা সমাধান।

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

প্রথম সরল উপায়¶

প্রথম সরল চিন্তা: 1 থেকে শুরু করে বারবার 2 দিয়ে গুণ করতে থাকো, যতক্ষণ না n ছুঁই বা পেরিয়ে যাই।

উদাহরণ

p = 1
while p < n:
    p = p * 2
return p == n     (এবং n > 0)

কোথায় বেশি কাজ হচ্ছে¶

আসলে এই loop-ভিত্তিক version মন্দ নয় — O(log n)। কিন্তু "সবচেয়ে সরল" brute force হলো 1 থেকে n পর্যন্ত প্রতিটা সংখ্যাকে power হিসেবে যাচাই করা, যা O(n)। মূল শিক্ষা: divisibility বুঝলে আমরা পুরো range না ঘেঁটে শুধু log n বার halving করেই উত্তর পাই — অপ্রয়োজনীয় গোনা বাদ যায়।

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

মূল observation: 2-এর power-কে বারবার 2 দিয়ে ভাগ করলে কখনো বিজোড় ভাগশেষ আসে না, আর ঠিক 1-এ থামে। তাই কোনো ধাপে n % 2 != 0 (এবং n != 1) পেলেই সাথে সাথে False। আর শুরুতেই n <= 0 বাদ দিতে হবে, কারণ power of two সবসময় ধনাত্মক।

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

Base case দুটো আগে সামলাও: n == 1 → True; n <= 0 বা n বিজোড় (n % 2 == 1) → False। নাহলে n জোড়, তাই is_pow(n // 2)-এ leap of faith নিয়ে recurse করো। প্রতি ধাপে n অর্ধেক হয়, তাই মাত্র O(log n) ধাপ। (Bit-trick n > 0 and n & (n-1) == 0-ও আছে, কিন্তু recursion chapter-এ halving-টাই শেখার লক্ষ্য।)

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

মোচড়: "এটা কি 2-এর power?" সরাসরি যাচাই করার বদলে জিজ্ঞেস করো "এটাকে অর্ধেক করলে কি ছোট একটা 2-এর power পাই?" বড় প্রশ্নটা এক ধাপ ছোট একই প্রশ্নে নেমে আসে, আর base case (1 বা বিজোড়) সাথে সাথে উত্তর দেয়।

ছবিতে বোঝা¶

প্রতি call-এ n অর্ধেক হয় — single-branch (linear) recursion, halving বলে গভীরতা log n:

উদাহরণ

is_pow(16)
   └ 16 জোড় -> is_pow(8)
        └ 8 জোড় -> is_pow(4)
             └ 4 জোড় -> is_pow(2)
                  └ 2 জোড় -> is_pow(1)
                       └ n == 1 -> True   ✓

is_pow(12)
   └ 12 জোড় -> is_pow(6)
        └ 6 জোড় -> is_pow(3)
             └ 3 বিজোড়, 1 নয় -> False   ✗

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

is_power_of_two(8):

n = 8: 8 > 0, 8 % 2 == 0 → জোড়; recurse is_pow(4)।
n = 4: জোড় → recurse is_pow(2)।
n = 2: জোড় → recurse is_pow(1)।
n = 1: base case → return True।
সব call True ফেরত পাঠায় → চূড়ান্ত উত্তর True। (তুলনায় is_pow(6): 6→3, 3 বিজোড় ≠ 1 → False।)

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

Python¶

Python

def is_power_of_two(n):
    if n == 1:                 # base case: 2^0 = 1
        return True
    if n <= 0 or n % 2 != 0:   # ধনাত্মক নয়, বা বিজোড় (1 ছাড়া) -> না
        return False
    return is_power_of_two(n // 2)   # জোড়: অর্ধেক করে recurse

# ---- tests ----
assert is_power_of_two(1) is True       # 2^0
assert is_power_of_two(2) is True       # 2^1
assert is_power_of_two(16) is True      # 2^4
assert is_power_of_two(1024) is True    # 2^10
assert is_power_of_two(3) is False
assert is_power_of_two(0) is False      # শূন্য
assert is_power_of_two(-16) is False    # ঋণাত্মক
assert is_power_of_two(6) is False      # 6 -> 3 (বিজোড়)
assert [is_power_of_two(x) for x in [1, 2, 4, 8]] == [True, True, True, True]
print("সব test pass!")

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

if n == 1: return True — সবচেয়ে ছোট 2-এর power; recursion এখানে থামে।
if n <= 0 or n % 2 != 0: return False — দুটো fail condition একসাথে: অ-ধনাত্মক, অথবা বিজোড় (যা 1 নয়)।
return is_power_of_two(n // 2) — n জোড় বলে অর্ধেক করে ছোট সংখ্যার উপর leap of faith।
guard-গুলো base case আগে রাখায় বিজোড় বা শূন্য ইনপুট নিরাপদে ধরা পড়ে।

Output মিলিয়ে দেখা¶

is_power_of_two(16): 16→8→4→2→1, প্রতি ধাপ জোড়, শেষে True। is_power_of_two(6): 6→3, 3 বিজোড় ও 1 নয় → False। 0 ও -16 প্রথম guard-এই False। list-comprehension assert প্রমাণ করে 1,2,4,8 সবই power, তারপর print: সব test pass!।

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

সময়¶

O(log n) — প্রতি call n অর্ধেক করে, তাই গভীরতা log₂ n।

অতিরিক্ত জায়গা¶

O(log n) — call stack-এর গভীরতা log n; কোনো extra data structure নেই। (Iterative বা bit-trick দিয়ে O(1) করা যায়।)

যে ভুলগুলো এড়াতে হবে¶

n <= 0 guard ভুলে যাওয়া — 0 infinite recurse করে (0 // 2 == 0), আর ঋণাত্মক ভুল ফল দেয়।
base case n == 1 না রেখে শুধু বিজোড় check করা — তখন কখনো True ফেরত আসে না।
n % 2 == 0 আর n == 1 এর ক্রম গুলিয়ে ফেলা — 1 কে আগে আলাদা করে handle করতেই হবে।
float division n / 2 ব্যবহার করা — integer // রাখো, নাহলে তুলনা বিগড়ে যায়।

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

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

ভিত্তি: divisibility ও modulo arithmetic (math fundamentals)। ../patterns.md-এর Pattern 1 (decrease-and-conquer) দেখো — এখানে "decrease" মানে অর্ধেক করা, halving। Power of Four-এর সাথে তুলনা করলে একই কাঠামো % 4 দিয়ে।

পরের অনুশীলন¶

Power of Three — https://leetcode.com/problems/power-of-three/
Power of Four — https://leetcode.com/problems/power-of-four/
Pow(x, n) (এর সরাসরি বড় ভাই) — https://leetcode.com/problems/powx-n/ (এই tracker-এর #5)

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

Halving decrease-and-conquer: বারবার নির্দিষ্ট factor (এখানে 2) দিয়ে ভাগ করে problem-কে log n ধাপে base-এ নামানো; divisibility check-ই decision। যেকোনো "power of k" প্রশ্নে এই pattern সরাসরি খাটে।

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

ভবিষ্যতের আমাকে: "Power of two = বারবার 2 দিয়ে ভাগ, ঠিক 1-এ থামলে True; বিজোড় বা ≤0 হলে False।" যখনই কোনো প্রশ্ন 'এটা কি কোনো base-এর power' বা 'বারবার সমান ভাগ করা যায় কি' — এই halving + divisibility pattern মনে করবে।

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