Problem link ও উৎস
- **Original source:** LeetCode — Power of Two
- **Platform:** LeetCode —
- **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)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#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`
### Input ও output {#6-example-input-and-output}
```text
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।)
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা পরিবার যেখানে ঠিক **একজন** কর্তা থাকার নিয়ম। তুমি যাচাই করতে চাও — পরিবারে কি ঠিক একজন কর্তা?
`n & (n - 1)` যেন বলছে — "একজন কর্তাকে সরিয়ে দিলাম, এখন কি আর কেউ কর্তা আছে?" যদি সরানোর পর কেউ না থাকে (`== 0`), মানে শুরুতে ঠিক একজনই ছিল → power of two।
কিন্তু খালি পরিবার (`n = 0`, কোনো কর্তাই নেই) — সেও "সরানোর পর কেউ নেই" শর্ত মেটায়, অথচ সে power of two নয়! তাই আলাদা করে `n > 0` (অন্তত একজন আছে) যাচাই করতে হয়।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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 কিনা" প্রশ্নটার দ্রুততম উত্তর।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল observation: **2-এর power-এর binary-তে ঠিক একটা 1 থাকে, বাকি সব 0।**
```text
1 = 0001 2 = 0010 4 = 0100 8 = 1000
```
আর 058-এর trick মনে করো — `n & (n - 1)` সবচেয়ে নিচের জ্বলা bit মুছে দেয়। যদি সংখ্যায় ঠিক **একটা** bit জ্বলা থাকে, একবার মুছলেই 0! তাই:
```text
n & (n - 1) == 0 মানে "একটাই (বা শূন্যটা) set bit"
```
শূন্যটা বাদ দিতে `n > 0` শর্ত যোগ করি → এক লাইনে power-of-two check।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
trick না জানলে, সরাসরি ভাগ করতে থাকো — `n` কে বারবার 2 দিয়ে ভাগ করো; শেষে 1-এ পৌঁছালে power of two, মাঝপথে বিজোড় পেলে নয়:
```python
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)` এক ধাপেই উত্তর দেয়।
```text
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` শর্ত যোগ করে:
```python
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।
### ছবিতে বোঝা {#5-visual-explanation}
power of two-তে এক bit জ্বলা, তাই একবার মুছলেই 0:
```text
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 হয় না:
```text
n = 6 = 0 1 1 0
n - 1 = 0 1 0 1
--- --- --- ---
AND = 0 1 0 0 != 0 -> power of two নয় ✗
```
আর সেই ফাঁদ — `n = 0`:
```text
n = 0, n - 1 = -1 (Python: ...1111)
0 & (-1) = 0 -> শর্ত মেটে! কিন্তু 0 power of two নয়
তাই `n > 0` দিয়ে আগেই আটকাই
```
### ছোট input-এ ধাপে ধাপে {#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 আর গণনাই হলো না)।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
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}
```text
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।
```text
return n > 0 and bin(n).count("1") == 1
```
বিকল্প: সরাসরি popcount গুনে দেখি ঠিক 1 কিনা — যাচাইয়ের জন্য।
`assert` লাইন আর `for` loop দুই method-কে আর সত্যিকারের 2-এর power-এর set-এর সাথে 0 থেকে 1999 পর্যন্ত মিলিয়ে নিচ্ছে। সব ঠিক থাকলে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
True
False
False
সব test pass!
```
প্রথম তিন লাইন তিনটা `print` থেকে: 8→True, 6→False, 0→False (edge case ঠিকঠাক আটকেছে)। সব `assert` (cross-check loop সহ) চুপচাপ pass করেছে। শেষে `সব test pass!`।
### JavaScript ও test cases {#21-javascript-solution-with-test-cases}
এক লাইনের সেই চাল — কিন্তু `n > 0` শর্ত ভুললে JS-এও `0` ফাঁদে ফেলবে (`0 & -1 === 0`)।
```javascript
// 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 হয়ে যায়।
### TypeScript ও test cases {#22-typescript-solution-with-test-cases}
```typescript
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