004 — Power of Two¶

Source¶

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)

1. Problem in simple words¶

একটা 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

2. Which basic idea does this inherit from?¶

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

3. What is the hidden math or logic?¶

লুকানো 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।

4. Which data structure is needed?¶

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

5. Why this data structure fits¶

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

6. Real-life analogy¶

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

7. Visual explanation¶

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

8. Example input and 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

9. Brute force thinking¶

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

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

10. Why brute force is slow¶

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

11. Key observation¶

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

12. Optimized intuition¶

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-টাই শেখার লক্ষ্য।)

13. Thinking tweak¶

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

14. Step-by-step dry run¶

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

15. Python solution¶

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

16. Line-by-line code explanation¶

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 আগে রাখায় বিজোড় বা শূন্য ইনপুট নিরাপদে ধরা পড়ে।

17. Output walkthrough¶

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

18. Time complexity¶

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

19. Space complexity¶

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

20. Common mistakes¶

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 // রাখো, নাহলে তুলনা বিগড়ে যায়।

21. Which basic problem this inherits from¶

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

22. Similar harder problems¶

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)

23. Pattern learned¶

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

24. Final summary¶

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