Problem link ও উৎস
- **Original source:** LeetCode Sqrt(x)
- **Platform:** LeetCode —
- **Topic:** Math-based programming fundamentals → Level 7: Binary Search on Answer
- **Difficulty:** Easy
- **Pattern:** first BSoA (answer space-এর উপর প্রথম binary search)
- **Basic idea inherited from:** 091 — Basic Binary Search
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা অঋণাত্মক integer `x` দেওয়া। তার বর্গমূলের **floor** (নিচের দিকে পূর্ণসংখ্যা) বের করো — মানে সবচেয়ে বড় integer `r` যেন `r * r <= x`।
দশমিক অংশ ফেলে দিতে হবে: `sqrt(8)` ≈ 2.828, কিন্তু উত্তর **2** (কারণ 2² = 4 ≤ 8, আর 3² = 9 > 8)। `sqrt(16)` = 4 হুবহু, তাই উত্তর 4।
শর্ত: কোনো `math.sqrt`, `** 0.5`, বা pow ব্যবহার না করে — শুধু integer গণিতে। এটাই problem-টাকে binary search-এর জন্য নিখুঁত বানায়।
### Input ও output {#6-example-input-and-output}
```text
x -> floor(√x) (ব্যাখ্যা)
--------------------------------
8 -> 2 (2²=4 ≤ 8 < 9=3²)
16 -> 4 (4²=16 হুবহু)
17 -> 4 (4²=16 ≤ 17 < 25)
0 -> 0 (√0 = 0)
1 -> 1 (√1 = 1)
2 -> 1 (1²=1 ≤ 2 < 4)
2147483647 -> 46340 (বড় সংখ্যা; overflow-হীন)
```
edge case: **0 আর 1** আলাদা করে যাচাই করো (অনেক sqrt bug এখানেই)। আর বড় x-এ Python-এ overflow নেই, কিন্তু অন্য ভাষায় `mid * mid` overflow করতে পারে — মনে রেখো।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো তুমি একটা বর্গাকার বাগান বানাতে চাও যার ক্ষেত্রফল ঠিক `x` বর্গফুটের মধ্যে থাকবে (বেশি না)। প্রশ্ন: বাহুটা সবচেয়ে বেশি কত ফুট রাখতে পারো?
তুমি অনুমান করো — "বাহু 5 ফুট?" তাহলে ক্ষেত্রফল 25। x = 20 হলে 25 > 20, বড় হয়ে গেছে, ছোট করো। "বাহু 4?" → 16 ≤ 20, চলে; আরও বড় চেষ্টা করো। "বাহু 5?" আবার বড়। তাই উত্তর 4।
প্রতিবার একটা বাহু অনুমান করে "ক্ষেত্রফল কি ধরে যায়?" যাচাই করছ — আর অর্ধেক সম্ভাবনা বাদ দিচ্ছ। এটাই BSoA।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
091 (Basic Binary Search)-এর `lo`/`hi`/`mid` কাঠামো থেকে — কিন্তু একটা যুগান্তকারী বদল: **`a[mid]`-এর জায়গায় একটা computed check `mid * mid <= x`।**
091-এ আমরা একটা সত্যিকারের array-র ঘর দেখতাম। এখানে কোনো ঘর নেই — `mid` নিজেই একটা সম্ভাব্য উত্তর, আর আমরা তাকে formula দিয়ে যাচাই করি। এই "array → answer space" আর "lookup → check" — এই দুই প্রতিস্থাপনই BSoA-র জন্ম, আর এটাই 096-102-এর ভিত্তি।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea — **Binary Search on Answer (BSoA)**। কোনো array নেই, কিন্তু একটা **check** আছে: "`m * m <= x`?" আর এই check-এর উত্তরগুলো m-এর ক্রমে সাজালে একটা monotonic সিঁড়ি **T T T F F F** — প্রথমে সব সত্যি, একটা জায়গার পরে চিরকাল মিথ্যা।
সেই **শেষ T**-টাই floor(√x)। monotonic সিঁড়ি মানেই binary search চলে — তা সে array হোক বা না হোক।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সবচেয়ে সরল — 0 থেকে শুরু করে এক এক করে গুনতে থাকো, যতক্ষণ `r * r` x ছাড়িয়ে না যায়:
```python
def my_sqrt_brute(x):
r = 0
while (r + 1) * (r + 1) <= x:
r += 1
return r
```
এটা ঠিক উত্তরই দেয় — প্রতিবার চেক করে "পরের সংখ্যাটার বর্গ এখনো x-এর মধ্যে?" যতক্ষণ হ্যাঁ, এগিয়ে যাও। থেমে গেলে হাতে থাকা `r`-ই floor(√x)।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
সমস্যা — loop চলে √x বার। ছোট x-এ ঠিক আছে, কিন্তু x = 2,000,000,000 হলে √x ≈ 45,000 — তবু ঠিক আছে মনে হতে পারে। কিন্তু এটা আসলে **O(√x)**, যা x-এর সাথে দ্রুত বাড়ে।
```text
x = 10^18 হলে:
brute force : ~10^9 বার loop (√x; অনেক ধীর, TLE)
binary search : ~60 বার (log₂(x); চোখের নিমেষে)
```
মূল শিক্ষা: উত্তর monotonic হলে এক এক করে গোনা অপচয় — অর্ধেক-অর্ধেক বাদ দেওয়া যায়।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight: "`m² <= x`"-এর সিঁড়ি **T T T F F F** — monotonic। তাই উত্তর-জগৎ `[0, x]`-এ binary search করে শেষ T খুঁজি:
```python
def my_sqrt(x):
lo, hi = 0, x + 1 # উত্তর [0, x]-এর মধ্যে; hi = x+1 (প্রথম F-এর পরে)
while lo < hi:
mid = (lo + hi) // 2
if mid * mid <= x:
lo = mid + 1 # mid চলে (T) — আরও বড় চেষ্টা
else:
hi = mid # mid বড় (F) — ছোট করো
return lo - 1 # প্রথম F-এর আগেরটা = শেষ T
```
প্রতি ধাপে অর্ধেক → O(log x)।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!" মুহূর্ত — এটাই গোটা level-এর মূল মোচড়: **উত্তর সরাসরি বের করতে না পারলেও, উত্তর ধরে নিয়ে যাচাই করা যায় কি না দেখো — যাচাই সস্তা আর monotonic হলে binary search-ই উত্তর খুঁজে দেবে।**
এখানে √x-এর সরাসরি formula আমরা ব্যবহার করছি না; বরং "এই m কি ছোট-সমান √x?" — এই হ্যাঁ/না প্রশ্নই যথেষ্ট। array লাগে না, শুধু একটা monotonic check লাগে। এই decomposition (answer space + check) মাথায় গেঁথে নাও — 096 থেকে 102 প্রতিটাতে এটাই ফিরবে, শুধু check-টা বদলাবে।
### ছবিতে বোঝা {#5-visual-explanation}
`x = 17`। প্রতিটা সম্ভাব্য উত্তর m-এর জন্য "`m² <= 17`?":
```text
m = 1 2 3 4 | 5 6 7 ...
m*m = 1 4 9 16 |25 36 49 ...
m²<=17 = T T T T | F F F ...
↑
শেষ T → floor(√17) = 4
(কারণ 4²=16 ≤ 17, কিন্তু 5²=25 > 17)
```
monotonic সিঁড়ি **T T T F F F** — একবার F শুরু হলে আর T ফেরে না (m বাড়লে m² শুধু বাড়ে)। তাই binary search-এ শেষ T খুঁজি।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`x = 17` চালাই (`hi = 18`):
| step | lo | hi | mid | mid*mid | ≤ 17? | সিদ্ধান্ত |
| --- | --- | --- | --- | --- | --- | --- |
| 1 | 0 | 18 | 9 | 81 | না | hi = mid = 9 |
| 2 | 0 | 9 | 4 | 16 | হ্যাঁ | lo = mid + 1 = 5 |
| 3 | 5 | 9 | 7 | 49 | না | hi = mid = 7 |
| 4 | 5 | 7 | 6 | 36 | না | hi = mid = 6 |
| 5 | 5 | 6 | 5 | 25 | না | hi = mid = 5 |
| — | 5 | 5 | — | — | — | lo == hi = 5 → return 5 - 1 = 4 |
উত্তর 4 ✓। লক্ষ করো: loop শেষে `lo = 5` হলো **প্রথম F**-এর index, আর `lo - 1 = 4` হলো **শেষ T** — আমাদের floor(√17)।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def my_sqrt(x):
"""floor(sqrt(x)) — শুধু integer গণিতে, binary search-এ।"""
if x < 2: # 0 আর 1-এর জন্য √x = x
return x
lo, hi = 1, x # উত্তর [1, x]-এর মধ্যে (x≥2 বলে)
while lo < hi:
mid = (lo + hi + 1) // 2 # উপরে ঝোঁকানো mid (lo = mid থাকায়)
if mid * mid <= x:
lo = mid # mid চলে (T) — রেখে আরও বড় চেষ্টা
else:
hi = mid - 1 # mid বড় (F) — নিশ্চিত বাদ
return lo
import math
def my_sqrt_brute(x):
r = 0
while (r + 1) * (r + 1) <= x:
r += 1
return r
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert my_sqrt(8) == 2
assert my_sqrt(16) == 4 # হুবহু বর্গ
assert my_sqrt(17) == 4
assert my_sqrt(0) == 0 # edge
assert my_sqrt(1) == 1 # edge
assert my_sqrt(2) == 1
assert my_sqrt(2147483647) == 46340 # বড় সংখ্যা
# math.isqrt আর brute force-এর সাথে cross-check
for x in range(0, 1000):
assert my_sqrt(x) == math.isqrt(x)
assert my_sqrt(x) == my_sqrt_brute(x)
# floor-এর সংজ্ঞা সরাসরি যাচাই: r² ≤ x < (r+1)²
for x in [5, 26, 99, 100, 101, 12345]:
r = my_sqrt(x)
assert r * r <= x < (r + 1) * (r + 1)
print(my_sqrt(8)) # 2
print(my_sqrt(16)) # 4
print(my_sqrt(17)) # 4
print("সব test pass!")
```
> দুটো ভিন্ন কিন্তু সমান-শুদ্ধ template আছে: section 9-এর "FFF...→ শেষ T = lo−1" আর section 12-এর "maximize: lo=mid, উপরে-ঝোঁকা mid"। দুটোই ঠিক উত্তর দেয়; এখানে maximize রূপটা ব্যবহার করলাম কারণ এটা "শেষ T সরাসরি ফেরায়" — 098-এর সাথে মেলে।
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
if x < 2: return x
```
0 আর 1-এর জন্য √x = x (√0=0, √1=1)। এই গুরুত্বপূর্ণ edge case আলাদা করে সামলাই, যাতে নিচের range নিরাপদ থাকে।
```text
lo, hi = 1, x
```
x ≥ 2 বলে উত্তর অন্তত 1, আর বড়জোর x (যদিও বাস্তবে অনেক ছোট)। তাই answer space `[1, x]`।
```text
mid = (lo + hi + 1) // 2
```
`+1` দিয়ে mid **উপরে** ঝোঁকানো — কারণ নিচে `lo = mid` আছে। নইলে `hi - lo == 1` অবস্থায় `mid = lo` হয়ে `lo = mid` কোনো অগ্রগতি করত না → infinite loop।
```text
if mid * mid <= x: lo = mid
```
mid² এখনো x-এর মধ্যে — mid একটা বৈধ উত্তর (T)। তাকে ফেলো না (`lo = mid`), বরং আরও বড় চেষ্টা করো।
```text
else: hi = mid - 1
```
mid² x ছাড়িয়ে গেছে (F) — mid নিশ্চিত উত্তর না। তাই mid সহ ডান দিক বাদ।
cross-check-এ `math.isqrt` (Python-এর built-in integer sqrt) আর brute force দুটোর সাথে, এবং floor-এর সংজ্ঞা (`r² ≤ x < (r+1)²`) সরাসরি যাচাই করছি। সব মিললে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
2
4
4
সব test pass!
```
প্রথম: `my_sqrt(8)` = 2 (2²=4 ≤ 8 < 9)। দ্বিতীয়: `my_sqrt(16)` = 4 (হুবহু বর্গ)। তৃতীয়: `my_sqrt(17)` = 4 (4²=16 ≤ 17 < 25)। আগের সব `assert` — `math.isqrt` cross-check (0-999), brute force, আর floor সংজ্ঞা যাচাই — চুপচাপ pass। সবশেষে `সব test pass!`।
### JavaScript ও test cases {#21-javascript-solution-with-test-cases}
answer space-এর উপর binary search — array নেই, check `mid * mid <= x`। `lo = mid` রাখায় mid **উপরে** ঝোঁকাই।
```javascript
// throwing assert — fail করলে থেমে error দেবে
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
function mySqrt(x) {
if (x < 2) return x; // 0, 1-এর জন্য √x = x
let lo = 1, hi = x; // উত্তর [1, x]
while (lo < hi) {
const mid = Math.floor((lo + hi + 1) / 2); // +1: lo = mid থাকায় উপরে ঝোঁকা
if (mid * mid <= x) lo = mid; // mid চলে (T) → রেখে বড় চেষ্টা
else hi = mid - 1; // mid বড় (F) → বাদ
}
return lo;
}
// brute — cross-check
const sqrtBrute = (x) => { let r = 0; while ((r + 1) * (r + 1) <= x) r++; return r; };
// ---- test cases (file-এর example + edge case) ----
assert(mySqrt(8) === 2, "2²=4 ≤ 8 < 9");
assert(mySqrt(16) === 4, "হুবহু বর্গ");
assert(mySqrt(17) === 4, "4²=16 ≤ 17 < 25");
assert(mySqrt(0) === 0, "edge 0");
assert(mySqrt(1) === 1, "edge 1");
assert(mySqrt(2) === 1, "2");
assert(mySqrt(2147483647) === 46340, "বড় সংখ্যা");
// brute-এর সাথে 0..999 জুড়ে মিল + floor সংজ্ঞা r² ≤ x < (r+1)²
for (let x = 0; x < 1000; x++) {
assert(mySqrt(x) === sqrtBrute(x), "cross " + x);
const r = mySqrt(x);
assert(r * r <= x && x < (r + 1) * (r + 1), "floor def " + x);
}
console.log("সব JS test pass!");
```
> **JS টীকা:** `lo = mid` রাখলে mid অবশ্যই **উপরে** ঝোঁকাও (`(lo + hi + 1) / 2`), নাহলে `hi - lo === 1`-এ `mid === lo` হয়ে কোনো অগ্রগতি না করে infinite loop। `mid * mid` JS number-এ 2^53 পর্যন্ত নিরাপদ (2147483647²-ও ঠিক); তার বেশি হলে `mid <= Math.floor(x / mid)` বা BigInt লাগে।
### TypeScript ও test cases {#22-typescript-solution-with-test-cases}
```typescript
function mySqrt(x: number): number {
if (x < 2) return x;
let lo = 1, hi = x;
while (lo < hi) {
const mid = Math.floor((lo + hi + 1) / 2);
if (mid * mid <= x) lo = mid;
else hi = mid - 1;
}
return lo;
}
function expect(actual: number, expected: number, msg = ""): void {
if (actual !== expected) throw new Error(`FAIL ${msg}: ${actual}`);
}
const cases: ReadonlyArray