69. Sqrt(x)

Problem

Bài toán yêu cầu tìm căn bậc hai nguyên của một số nguyên không âm x, tức la tìm số nguyên lớn nhất y sao cho y^2 ≤ x. Không được dùng các hàm căn bậc hai và phép lũy thừa có sẵn

Approach - Binary search

Tìm kiếm nhị phân trong đoạn [1, x] (hoặc [0,x] nếu muốn bao cả 0), kiểm tra mid * mid so với để thu hẹp khoảng cách tìm kiếm. Khi kết thúc, return về giá trị lớn nhất sao cho bình phương không vượt quá x. Cách này tối ưu với độ phức tạp O(logx)

Giải thích chi tiết về binary search

Nếu x<2, trả về x luôn vì căn bậc hai của 0 và 1 là chính nó.

Khởi tạo left = 1, right = x.

Trong vòng lặp:

Tính mid = left + Math.floor((right - left) / 2).

Nếu mid*mid == x, trả về mid.

Nếu mid*mid < x, cập nhật left = mid + 1.

Nếu mid*mid > x, cập nhật right = mid - 1.

Kết thúc vòng lặp, trả về right vì right là số nguyên lớn nhất mà bình phương không vượt quá

Time and space complexity

TC: O(logx)

SC: O(1)

Solution

typescripttypescript

1function mySqrt(x: number): number {
2    if(x < 2) return x;
3    let left = 1, right = x;
4    while(left <= right) {
5	    const mid = left + Math.floor((right - left) / 2);
6	    const square = mid * mid;
7	    if(square === x) return mid
8	    else if (square < x) left = mid + 1
9	    else right = mid - 1
10    }
11    return right
12};

💡

Tóm tắt

Ý tưởng tốt nhất là dùng Binary Search để tìm căn bậc hai nguyên.

Không dùng hàm có sẵn, không cần kiểm tra từng số một.

💡

Deep dive

Nếu bạn cần tìm số nhỏ nhất thỏa mãn điều kiện (VD: nhỏ nhất ≥ x, hay “first true”), bạn sẽ return left sau khi vòng lặp kết thúc. Điều này đúng vì khi kết thúc, left là chỉ số đầu tiên mà điều kiện đúng

Nếu ban cần tìm số lớn nhất thỏa mãn điều kiện (VD lớn nhất ≤ x, hay “last true”), bạn sẽ return right au khi vòn lặp kết thúc. Vì right là chỉ số cuối cùng mà điều kiện còn đúng

Minh họa:

Tìm lower bound (nhỏ nhất ≥ x): return left.

Tìm upper bound (lớn nhất ≤ x): return right.

Tóm lại

Tìm số lớn hơn hoặc bằng: return left

Tìm số nhỏ hơn hoặc bằng: return right

Lower bound

Lower bound là chỉ số đầu tiên trong mảng mà giá trị tại đó lớn hơn hoặc bằng giá trị cần tìm (x)

Nói cách khác, lower bound return về vị trí nhỏ nhất mà arr[idx] >= x trong mảng đã sắp xếp tăng dần

Upper bound

Upper bound là chỉ số đầu tiên trong mảng mà giá trị tại đó lớn hơn giá trị cần tìm (x)

Nói cách khác, upper bound return về vị trí nhỏ nhất mà arr[idx] > x trong mảng tăng dần

Loading content...

1function mySqrt(x: number): number { 2 if(x < 2) return x; 3 let left = 1, right = x; 4 while(left <= right) { 5 const mid = left + Math.floor((right - left) / 2); 6 const square = mid * mid; 7 if(square === x) return mid 8 else if (square < x) left = mid + 1 9 else right = mid - 1 10 } 11 return right 12};

Related Posts

Related Posts

69. Sqrt(x)

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists