059 — Power of Two

058-এ শেখা n & (n - 1) trick-টার সবচেয়ে সুন্দর প্রয়োগ এটা। একটা সংখ্যা 2-এর power কিনা (1, 2, 4, 8, 16, ...) এক লাইনে বলে দেওয়া। চাবি: 2-এর power মানে binary-তে ঠিক একটা 1। interview-তে এটা খুব common warm-up। একটা ছোট কিন্তু খতরনাক edge case আছে — n = 0 — সেটাও দেখব। চলো।

Source

• Original source: LeetCode — Power of Two
• Platform: LeetCode — https://leetcode.com/problems/power-of-two/
• Topic: Math-based programming fundamentals → Level 4: Bit Manipulation → single set bit check
• Difficulty: Easy
• Pattern: n & (n - 1) == 0 (একটাই set bit আছে কিনা)
• Basic idea inherited from: 058 — Count Set Bits (n & (n - 1) trick)

1. Problem in simple words

একটা integer n দেওয়া আছে। বলতে হবে এটা 2-এর কোনো power কিনা — মানে n = 2^k (কোনো k ≥ 0-এর জন্য) হয় কিনা।

2-এর power গুলো: 1, 2, 4, 8, 16, 32, 64, ... (এখানে 1 = 2^0)।

• 8 → হ্যাঁ (2^3) → True
• 6 → না (2 × 3) → False
• 1 → হ্যাঁ (2^0) → True
• 0 → না → False

2. What is the math idea?

মূল observation: 2-এর power-এর binary-তে ঠিক একটা 1 থাকে, বাকি সব 0।

1  = 0001     2 = 0010     4 = 0100     8 = 1000

আর 058-এর trick মনে করো — n & (n - 1) সবচেয়ে নিচের জ্বলা bit মুছে দেয়। যদি সংখ্যায় ঠিক একটা bit জ্বলা থাকে, একবার মুছলেই 0! তাই:

n & (n - 1) == 0   মানে   "একটাই (বা শূন্যটা) set bit"

শূন্যটা বাদ দিতে n > 0 শর্ত যোগ করি → এক লাইনে power-of-two check।

3. Which basic idea does this inherit from?

সরাসরি 058 (Count Set Bits)-এর n & (n - 1) trick-এর উপর দাঁড়িয়ে। 058-এ এটা দিয়ে সব জ্বলা bit গুনতে; এখানে শুধু জানতে চাই "ঠিক একটা bit জ্বলা কিনা" — তাই একবার মুছেই দেখি 0 হয় কিনা, পুরো গুনতে হয় না।

বলতে পারো 059 হলো 058-এর special case — "popcount ঠিক 1 কিনা" প্রশ্নটার দ্রুততম উত্তর।

4. Real-life analogy

ভাবো একটা পরিবার যেখানে ঠিক একজন কর্তা থাকার নিয়ম। তুমি যাচাই করতে চাও — পরিবারে কি ঠিক একজন কর্তা?

n & (n - 1) যেন বলছে — "একজন কর্তাকে সরিয়ে দিলাম, এখন কি আর কেউ কর্তা আছে?" যদি সরানোর পর কেউ না থাকে (== 0), মানে শুরুতে ঠিক একজনই ছিল → power of two।

কিন্তু খালি পরিবার (n = 0, কোনো কর্তাই নেই) — সেও "সরানোর পর কেউ নেই" শর্ত মেটায়, অথচ সে power of two নয়! তাই আলাদা করে n > 0 (অন্তত একজন আছে) যাচাই করতে হয়।

5. Visual explanation

power of two-তে এক bit জ্বলা, তাই একবার মুছলেই 0:

n = 8 = 1 0 0 0
n - 1 = 0 1 1 1     (একমাত্র 1 ভাঙল, ডানে সব 1)
        --- --- --- ---
AND   = 0 0 0 0     == 0  ->  power of two ✓

power of two নয় (দুই bit জ্বলা), তাই মুছেও 0 হয় না:

n = 6 = 0 1 1 0
n - 1 = 0 1 0 1
        --- --- --- ---
AND   = 0 1 0 0     != 0  ->  power of two নয় ✗

আর সেই ফাঁদ — n = 0:

n = 0, n - 1 = -1 (Python: ...1111)
0 & (-1) = 0   ->  শর্ত মেটে! কিন্তু 0 power of two নয়
তাই `n > 0` দিয়ে আগেই আটকাই

6. Example input and output

n    ->  output
---------------
8    ->  True       (2^3)
1    ->  True       (2^0)
16   ->  True       (2^4)
1024 ->  True       (2^10)
6    ->  False      (2 × 3)
0    ->  False      (edge case! n > 0 শর্তে আটকায়)
3    ->  False      (11, দুই bit)
-4   ->  False      (negative, power of two নয়)

সবচেয়ে গুরুত্বপূর্ণ edge case n = 0 — n & (n - 1) এখানে 0 দেয়, তাই n > 0 না দিলে 0-ও ভুল করে "power of two" হয়ে যাবে। (README common mistake #4।)

7. Brute force thinking

trick না জানলে, সরাসরি ভাগ করতে থাকো — n কে বারবার 2 দিয়ে ভাগ করো; শেষে 1-এ পৌঁছালে power of two, মাঝপথে বিজোড় পেলে নয়:

def is_power_of_two_brute(n):
    if n <= 0:
        return False
    while n % 2 == 0:        # যতক্ষণ জোড়, 2 দিয়ে ভাগো
        n //= 2
    return n == 1            # শেষে 1 হলে power of two

কাজ করে — 8 → 4 → 2 → 1 (হ্যাঁ); 6 → 3 (3 জোড় নয়, থামল, ≠ 1, না)। কিন্তু loop চালাতে হয়।

8. Why brute force may be slow

brute force loop ঘোরে log₂(n) বার — খুব ধীর নয়, কিন্তু n & (n - 1) এক ধাপেই উত্তর দেয়।

n = 2^30:
  brute      : 30 বার ভাগ
  n & (n-1)  : 1 বার AND  (O(1))

মূল কথা: যেটা এক operation-এ জানা যায়, তার জন্য loop চালানো অপচয়। আর bit-trick টা মনে রাখলে interview-তে চটজলদি লেখা যায়।

9. Better thinking

n & (n - 1) == 0 দিয়ে এক লাইনে — শুধু n > 0 শর্ত যোগ করে:

def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0

কোনো loop নেই — একটা subtraction, একটা AND, একটা তুলনা। O(1)। n > 0 শর্তটা short-circuit করে 0 আর negative আগেই আটকায়।

10. Thinking tweak

আসল "আহা!" — power of two = ঠিক একটা set bit; আর একটা set bit আছে কিনা জানতে গোনার দরকার নেই — একবার n & (n - 1) করে দেখো 0 হয় কিনা।

058-এ n & (n - 1) দিয়ে সব bit গুনতাম। এখানে বুঝলাম — যদি সংখ্যায় ঠিক একটা bit থাকে, একবার মুছলেই 0। তাই পুরো popcount না করে এক ধাপেই উত্তর। কিন্তু সাথে মনে রাখতে হবে — n & (n - 1) == 0 শূন্যটা set bit-এর ক্ষেত্রেও সত্যি (0 নিজেই), তাই n > 0 দিয়ে 0-কে আলাদা করে আটকাও। এই একটা শর্ত ভুলে যাওয়াই এই problem-এর সবচেয়ে common bug।

11. Step-by-step dry run

n = 8:

step	কাজ	মান
1	n > 0?	হ্যাঁ
2	n - 1	7 (0111)
3	n & (n-1)	1000 & 0111 = 0000
4	== 0?	হ্যাঁ → True

উত্তর: True। এখন n = 6:

step	কাজ	মান
1	n > 0?	হ্যাঁ
2	n - 1	5 (0101)
3	n & (n-1)	0110 & 0101 = 0100
4	== 0?	না → False

আর n = 0: step 1-এ n > 0 মিথ্যা → short-circuit → False (AND আর গণনাই হলো না)।

12. Python solution

def is_power_of_two(n):
    """n যদি 2-এর কোনো power (1, 2, 4, 8, ...) হয় True, নাহলে False।"""
    return n > 0 and (n & (n - 1)) == 0


def is_power_of_two_count(n):
    """একই উত্তর popcount দিয়ে: ঠিক একটা set bit কিনা (যাচাইয়ের জন্য)।"""
    return n > 0 and bin(n).count("1") == 1


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert is_power_of_two(8) is True       # 2^3
assert is_power_of_two(1) is True       # 2^0
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(6) is False      # 2 × 3
assert is_power_of_two(0) is False      # edge case!
assert is_power_of_two(3) is False      # 11
assert is_power_of_two(-4) is False     # negative

# দুই method মেলে; আর সত্যিকারের 2-এর power-এর সাথে মিলিয়ে যাচাই
powers = {1 << k for k in range(0, 20)}   # {1, 2, 4, ..., 524288}
for x in range(0, 2000):
    expected = x in powers
    assert is_power_of_two(x) == expected
    assert is_power_of_two_count(x) == expected

print(is_power_of_two(8))     # True
print(is_power_of_two(6))     # False
print(is_power_of_two(0))     # False
print("সব test pass!")

13. Line-by-line explanation

return n > 0 and (n & (n - 1)) == 0

এটাই হৃদয়, দুই অংশে:

• n > 0 — অন্তত একটা bit থাকতে হবে; এটা মিথ্যা হলে Python short-circuit করে আর পরেরটা দেখেই না (তাই 0 আর negative নিরাপদে আটকায়)।
• (n & (n - 1)) == 0 — lowest set bit মুছে দেখি 0 হয় কিনা; হলে মানে শুরুতে ঠিক একটাই bit ছিল → power of two।

return n > 0 and bin(n).count("1") == 1

বিকল্প: সরাসরি popcount গুনে দেখি ঠিক 1 কিনা — যাচাইয়ের জন্য।

assert লাইন আর for loop দুই method-কে আর সত্যিকারের 2-এর power-এর set-এর সাথে 0 থেকে 1999 পর্যন্ত মিলিয়ে নিচ্ছে। সব ঠিক থাকলে সব test pass!।

14. Output walkthrough

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

True
False
False
সব test pass!

প্রথম তিন লাইন তিনটা print থেকে: 8→True, 6→False, 0→False (edge case ঠিকঠাক আটকেছে)। সব assert (cross-check loop সহ) চুপচাপ pass করেছে। শেষে সব test pass!।

15. Time complexity

O(1) — একটা subtraction, একটা AND, একটা তুলনা। n যত বড়ই হোক, কাজ একই — এক ধাপেই উত্তর।

16. Space complexity

O(1) — কোনো list/array নেই; কয়েকটা int মাত্র।

17. Common mistakes

1. n > 0 শর্ত ভুলে যাওয়া — সবচেয়ে বড় ভুল। 0 & (0 - 1) == 0 সত্যি, তাই n > 0 না দিলে 0-ও power of two হয়ে যায়! (README #4।)
2. negative ভুলে যাওয়া — -4 power of two নয়; n > 0 সেটাও আটকায়।
3. Precedence ফাঁদ — n & (n - 1) == 0 মানে n & ((n-1) == 0)! সবসময় (n & (n - 1)) == 0।
4. == ভুলে = লেখা — তুলনায় সবসময় ==।
5. 1-কে বাদ দেওয়া — 1 = 2^0 একটা power of two; অনেকে ভুলে যায়।

18. Harder problems that inherit this idea

• LeetCode — Power of Four (https://leetcode.com/problems/power-of-four/) — power of two + অতিরিক্ত শর্ত (সেট bit জোড় position-এ)।
• 058 — Count Set Bits (এই repo) — এর জনক trick।
• LeetCode — Number of 1 Bits (https://leetcode.com/problems/number-of-1-bits/) — n & (n - 1)-এর সাধারণ রূপ।
• LeetCode — Reorder Power of 2 (https://leetcode.com/problems/reordered-power-of-2/) — digit permutation + power-of-two check।

19. Pattern learned

Single-set-bit check via n & (n - 1) == 0 — সাথে অবশ্যই n > 0। বড় শিক্ষা: power of two = ঠিক একটা set bit; একবার n & (n - 1) করে 0 হলেই হলো, পুরো গুনতে হয় না — কিন্তু 0-কে n > 0 দিয়ে আটকাতে ভুলো না।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "power of two = n > 0 and (n & (n - 1)) == 0। ঠিক একটা set bit থাকলেই 2-এর power; n > 0 শর্ত ভুলে গেলে 0 ফাঁদে ফেলবে। bracket আর precedence-এ সাবধান।"

পরের ধাপ → 060 — Odd One Out using XOR (এবার XOR-এর জাদুতে জোড়ার ভিড়ে একলা সংখ্যা খুঁজব)। সম্পর্কিত → 058 — Count Set Bits।

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

21. JavaScript solution (with test cases)

এক লাইনের সেই চাল — কিন্তু n > 0 শর্ত ভুললে JS-এও 0 ফাঁদে ফেলবে (0 & -1 === 0)।

// throwing assert — fail করলে থেমে error দেবে
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };

function isPowerOfTwo(n) {
  return n > 0 && (n & (n - 1)) === 0;   // n > 0 না দিলে 0 ভুল করে true
}

// popcount দিয়ে cross-check
const isPow2Count = (n) =>
  n > 0 && n.toString(2).split("").filter((c) => c === "1").length === 1;

// ---- test cases (file-এর example + edge case) ----
assert(isPowerOfTwo(8) === true, "2^3");
assert(isPowerOfTwo(1) === true, "2^0");
assert(isPowerOfTwo(16) === true, "2^4");
assert(isPowerOfTwo(1024) === true, "2^10");
assert(isPowerOfTwo(6) === false, "2x3");
assert(isPowerOfTwo(0) === false, "edge 0!");
assert(isPowerOfTwo(3) === false, "11");
assert(isPowerOfTwo(-4) === false, "negative");
// সত্যিকারের 2-এর power-এর সাথে 0..2000 জুড়ে মিল
const powers = new Set();
for (let k = 0; k < 20; k++) powers.add(1 << k);   // {1,2,4,...,524288}
for (let x = 0; x < 2000; x++) {
  const want = powers.has(x);
  assert(isPowerOfTwo(x) === want, "kern " + x);
  assert(isPow2Count(x) === want, "count " + x);
}
console.log("সব JS test pass!");

JS টীকা: n & (n - 1) == 0-এর আগে অবশ্যই (n & (n - 1)) === 0 — bracket জরুরি, কারণ &-এর precedence ===-এর চেয়ে কম। আর 0 আর negative আটকাতে n > 0 (short-circuit) প্রথমে রাখো; নাহলে 0 ভুল করে power of two হয়ে যায়।

22. TypeScript solution (with test cases)

function isPowerOfTwo(n: number): boolean {
  return n > 0 && (n & (n - 1)) === 0;
}

function expect(actual: boolean, expected: boolean, msg = ""): void {
  if (actual !== expected) throw new Error(`FAIL ${msg}: ${actual}`);
}

const cases: ReadonlyArray<readonly [number, boolean]> = [
  [8, true], [1, true], [16, true], [1024, true],
  [6, false], [0, false], [3, false], [-4, false],
];
for (const [n, want] of cases) expect(isPowerOfTwo(n), want, `pow2(${n})`);
console.log("সব TS test pass!");

TS টীকা: return type boolean দেওয়ায় ভুলে number ফেরালে (যেমন n & (n-1) সরাসরি return করা — যা number) compile-time-এ ধরা পড়ে; illegal states unrepresentable।

23. কোথায় কাজে লাগে (real-world use)

• Capacity / buffer sizing: hash table, ring buffer, memory pool প্রায়ই power-of-two আকারে — তখন index & (size - 1) দিয়ে দ্রুত modulo।
• Alignment check: memory address বা block power-of-two boundary-তে aligned কিনা যাচাই (low-level/embedded)।
• Graphics / textures: অনেক GPU texture mipmap power-of-two dimension চায়; upload-এর আগে validate।
• Fast scaling: power of two হলে multiply/divide কে cheap bit-shift দিয়ে করা যায়। মূল pattern — "ঠিক একটা set bit আছে কিনা এক operation-এ (n & (n-1) == 0, সাথে n > 0)" — single-bit isolation, flag validation জুড়ে বড় ছবিতে ফেরে।

---

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