095 — Square Root using Binary Search

এটাই এই level-এর হৃদয়, সবচেয়ে গুরুত্বপূর্ণ মোড়। এতক্ষণ binary search চলত একটা array-র উপর। কিন্তু এই problem-এ কোনো array নেই! তবু আমরা binary search চালাব — উত্তরের উপরেই। "⌊√x⌋ কত?" — উত্তর ধরে নাও, যাচাই করো, অর্ধেক বাদ দাও। এই মোড়টা — array থেকে answer space-এ — একবার বুঝে গেলে 096 থেকে 102 সব তোমার হাতের মুঠোয়। ধীরে, খুব ধীরে পড়ো।

Source

• Original source: LeetCode Sqrt(x)
• Platform: LeetCode — https://leetcode.com/problems/sqrtx/
• 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

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-এর জন্য নিখুঁত বানায়।

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 হোক বা না হোক।

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-এর ভিত্তি।

4. Real-life analogy

ভাবো তুমি একটা বর্গাকার বাগান বানাতে চাও যার ক্ষেত্রফল ঠিক x বর্গফুটের মধ্যে থাকবে (বেশি না)। প্রশ্ন: বাহুটা সবচেয়ে বেশি কত ফুট রাখতে পারো?

তুমি অনুমান করো — "বাহু 5 ফুট?" তাহলে ক্ষেত্রফল 25। x = 20 হলে 25 > 20, বড় হয়ে গেছে, ছোট করো। "বাহু 4?" → 16 ≤ 20, চলে; আরও বড় চেষ্টা করো। "বাহু 5?" আবার বড়। তাই উত্তর 4।

প্রতিবার একটা বাহু অনুমান করে "ক্ষেত্রফল কি ধরে যায়?" যাচাই করছ — আর অর্ধেক সম্ভাবনা বাদ দিচ্ছ। এটাই BSoA।

5. Visual explanation

x = 17। প্রতিটা সম্ভাব্য উত্তর m-এর জন্য "m² <= 17?":

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 খুঁজি।

6. Example input and output

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 করতে পারে — মনে রেখো।

7. Brute force thinking

সবচেয়ে সরল — 0 থেকে শুরু করে এক এক করে গুনতে থাকো, যতক্ষণ r * r x ছাড়িয়ে না যায়:

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-এর সাথে দ্রুত বাড়ে।

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 খুঁজি:

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-টা বদলাবে।

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

12. Python solution

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

if x < 2: return x

0 আর 1-এর জন্য √x = x (√0=0, √1=1)। এই গুরুত্বপূর্ণ edge case আলাদা করে সামলাই, যাতে নিচের range নিরাপদ থাকে।

lo, hi = 1, x

x ≥ 2 বলে উত্তর অন্তত 1, আর বড়জোর x (যদিও বাস্তবে অনেক ছোট)। তাই answer space [1, x]।

mid = (lo + hi + 1) // 2

+1 দিয়ে mid উপরে ঝোঁকানো — কারণ নিচে lo = mid আছে। নইলে hi - lo == 1 অবস্থায় mid = lo হয়ে lo = mid কোনো অগ্রগতি করত না → infinite loop।

if mid * mid <= x: lo = mid

mid² এখনো x-এর মধ্যে — mid একটা বৈধ উত্তর (T)। তাকে ফেলো না (lo = mid), বরং আরও বড় চেষ্টা করো।

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

14. Output walkthrough

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

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

15. Time complexity

O(log x) — answer space [1, x]-এ প্রতি ধাপে অর্ধেক, তাই log₂(x) ধাপ। 10^18-এর জন্যও মাত্র ~60 ধাপ। brute force-এর O(√x)-এর তুলনায় আকাশ-পাতাল।

(সূক্ষ্ম: প্রতি ধাপে mid * mid গুণ বড় সংখ্যায় digit-এর সাথে সামান্য খরচ বাড়ায়, কিন্তু interview-র মাপে আমরা একে O(log x) ধরি।)

16. Space complexity

O(1) — শুধু lo, hi, mid; কোনো array বা list না। input ছাড়া বাড়তি জায়গা প্রায় শূন্য।

17. Common mistakes

1. lo = mid কিন্তু mid নিচে ঝোঁকানো — mid = (lo + hi) // 2 রাখলে hi - lo == 1-এ infinite loop। lo = mid থাকলে mid উপরে ঝোঁকাও (+1)।
2. 0 আর 1 ভুলে যাওয়া — range [1, x] x=0-এ অর্থহীন; এই edge দুটো আলাদা করে সামলাও।
3. floor বনাম round গুলিয়ে ফেলা — sqrt(8)=2.82, কিন্তু উত্তর 2 (floor), 3 না। m * m <= x শর্তই floor নিশ্চিত করে।
4. mid * mid overflow (অন্য ভাষায়) — C++/Java-তে বড় x-এ mid * mid overflow করে; সেখানে mid <= x // mid লেখা নিরাপদ। Python-এ সমস্যা নেই।
5. answer space-এর hi ভুল — hi = x ঠিক (√x ≤ x সবসময় x≥1-এ); কিন্তু section 9-এর FFF template-এ hi = x + 1 দরকার ছিল — দুই template-এ hi-এর মানে আলাদা, গুলিও না।

18. Harder problems that inherit this idea

• LeetCode — Valid Perfect Square (https://leetcode.com/problems/valid-perfect-square/) — হুবহু এই binary search, শেষে r * r == x কিনা চেক।
• LeetCode — Pow(x, n) (https://leetcode.com/problems/powx-n/) — power-এর উপর ভিন্ন কৌশল (fast exponentiation), কিন্তু "computed check" চিন্তার আত্মীয়।
• 096 (Minimum Eating Speed) আর 102 (Kth Smallest) — এই repo-রই পরের ধাপ; এখানে শেখা "array নেই, check আছে" সেখানে minimize আর counting check হয়ে ফিরবে।

19. Pattern learned

Binary Search on Answer (BSoA), প্রথম দেখা — array-র জায়গায় answer space [lo, hi], lookup-এর জায়গায় computed check (mid² <= x)। বড় শিক্ষা: উত্তর সরাসরি গোনার দরকার নেই — একটা monotonic হ্যাঁ/না check থাকলেই binary search উত্তর খুঁজে দেয়, কোনো array ছাড়াই। এটাই 096-102-এর গোটা পরিবারের বীজ।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "floor(√x) = binary search on answer; check = mid² ≤ x, সিঁড়ি TTTFFF, শেষ T-ই উত্তর। array লাগে না — answer space + monotonic check-ই যথেষ্ট। 0/1 আলাদা সামলাই, lo=mid হলে mid উপরে ঝোঁকাই। এটাই BSoA-র জন্ম।"

পরের ধাপ → 096 — Minimum Eating Speed (প্রথম minimize ঘরানা: speed অনুমান করে "সময়ে শেষ হয়?" check)। সম্পর্কিত → 091 — Basic Binary Search।

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

21. JavaScript solution (with test cases)

answer space-এর উপর binary search — array নেই, check mid * mid <= x। lo = mid রাখায় mid উপরে ঝোঁকাই।

// 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 লাগে।

22. TypeScript solution (with test cases)

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<readonly [number, number]> = [
  [8, 2], [16, 4], [17, 4], [0, 0], [1, 1], [2, 1], [2147483647, 46340],
];
for (const [x, want] of cases) expect(mySqrt(x), want, `√${x}`);
console.log("সব TS test pass!");

TS টীকা: parameter ও return number declare করায় floor-sqrt-এর contract স্পষ্ট; ভুলে float/string পাঠানো compile-time-এ আটকায়। বড় x-এ overflow ভাবনা থাকলে signature bigint-এ বদলানোর সিদ্ধান্ত type-level-এই নেওয়া যায়।

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

• Answer space search: "সরাসরি গোনা যায় না, কিন্তু একটা guess যাচাই করা সহজ ও monotonic" — speed/capacity/threshold বের করার সব BSoA problem-এর বীজ।
• Integer sqrt without floats: big-integer/crypto context-এ floating point-এর rounding ভুল এড়াতে integer-only √।
• Geometry / sizing: বর্গাকার grid, tile, canvas-এর বাহু বের করা যাতে area একটা সীমার মধ্যে থাকে।
• Newton's method-এর বিকল্প: যেখানে নির্ভুল floor চাই আর monotonic check আছে, binary search নিরাপদ ও সহজ-প্রমাণযোগ্য। মূল pattern — "উত্তর সরাসরি না গুনে, monotonic হ্যাঁ/না check-এ binary search (array ছাড়াই)" — binary search on answer-এর গোটা পরিবারে বড় ছবিতে ফেরে।

---

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