Bài vỡ lòng trong khi học lập trình Java đó là kiểu integer nguyên thuỷ sẽ có int (32 bit) và long (64 bit). Kiểu long sẽ mô tả được số lớn hơn. Vâng ai cũng biết cả. Nhưng khi lập trình vẫn mắc phải lỗi sơ đẳng.

Ví dụ bài Leet Code số 69: Sqrt(x).

Yêu cầu của bài này

Cho một số nguyên không âm x, trả về căn bậc hai của x được làm tròn xuống số nguyên gần nhất. Số nguyên được trả về cũng không được âm.
Bạn không được sử dụng bất kỳ hàm hoặc toán tử lũy thừa tích hợp nào.

Ví dụ: không sử dụng pow(x, 0,5) trong c++ hoặc x ** 0,5 trong python.

Ví dụ 1:
Đầu vào: x = 4
Đầu ra: 2
Giải thích: Căn bậc hai của 4 là 2, vì vậy chúng tôi trả về 2.

Ví dụ 2:
Đầu vào: x = 8
Đầu ra: 2
Giải thích: Căn bậc hai của 8 là 2,82842…, và vì chúng ta làm tròn nó xuống số nguyên gần nhất, 2 được trả về.

Cách làm

Hướng giải của bài này là sử dụng Binary Search: lấy điểm giữa mid của dải số từ lo đến hi nếu:

  • mid * mid > x thì hi = mid
  • mid *mid < x thì low = mid +1

Code ban đầu của tôi như sau:

class Solution {
  public int mySqrt(int x) {
    int lo = 0, hi = x;
    while (hi > lo) {
      int mid = (hi + lo) / 2;
      int square_mid = mid * mid;
      if (square_mid > x) {
        hi = mid;
      } else if (square_mid < x) {
        lo = mid + 1;
      } else {
        return mid;
      }
    }
    if (lo * lo > x) {
      return lo - 1;
    } else {
      return lo;
    }
  }
}

Bộ unit test chạy đúng hết

@Test
void test() {
    assertThat(mySqrt(4)).isEqualTo(2);
    assertThat(mySqrt(8)).isEqualTo(2);
    assertThat(mySqrt(9)).isEqualTo(3);
    assertThat(mySqrt(16)).isEqualTo(4);
    assertThat(mySqrt(80)).isEqualTo(8);
    assertThat(mySqrt(2)).isEqualTo(1);
}

Khi x đủ lớn, hãy dùng long

Khi x là một số đủ lớn, đoạn code trên chạy không còn đúng nữa

assertThat(mySqrt(2147483647)).isEqualTo(46340);

Đoạn test trên sẽ trả về failed. Khi debug tôi thấy đoạn code này

int square_mid = mid * mid;

Khi mid đủ lớn thì bình phương của nó sẽ vượt giới hạn lưu trữ số nguyên dương biến kiển int 32 bit là 2^31 (trừ đi một bit mô tả dấu âm hay dương). Lúc này mid * mid trả về giá trị âm.

Vậy nguyên tắc trước khi bình phương một số kiểu int hãy ép kiểu sang long để tránh tình trạng tràn số

long square_mid = (long) mid * mid;

Code đầy đủ sau khi sửa lỗi

public int mySqrt(int x) {
 int lo = 0, hi = x;
 while (hi > lo) {
   int mid = (hi + lo) / 2;
   long square_mid = (long) mid * mid;
   if (square_mid > x) {
     hi =  mid;
   } else if (square_mid < x) {
     lo =  mid + 1;
   } else {
     return  mid;
   }
 }

 if ((long) lo * lo > x) {
   return lo - 1;
 } else {
   return lo;
 }