Đề bài yêu cầu đảo ngược thứ tự chữ số của một số nguyên trong khoảng [-2^31, 2^31 - 1], nếu số đảo ngược nằm ngoài khoảng trên, trả về kết quả bằng 0. Ngoài ra không được sử dụng kiểu dữ liệu số nguyên 64-bit.
Lời giải:
Không khó để nhận ra lời giải thông thường cho bài toán này, chúng ta chỉ việc thực hiện đảo ngược vị trí của các chữ số bằng phép chia và chia lấy dư cho 10, và lưu ý kiểm tra xem nó có vượt quá phạm vi số nguyên 32 bit hay không.
Tuy nhiên, có một quan sát khá thú vị có thể giúp tối ưu tốc độ chạy cho chương trình như sau:
Nhìn vào giá trị tối đa của kiểu số nguyên 32 bit là 2,147,483,647 (2^31 - 1), chúng ta thấy:
- Trong trường hợp chúng ta bắt đầu thêm chữ số thứ 10, mà giá trị của số đảo ngược đã vượt quá 214,748,364, thì bất kể chữ số thứ 10 là bao nhiêu, số đó sẽ có giá trị vượt quá 2,147,483,647.
- Nhưng nếu 9 chữ số đầu tiên không quá 214,748,364, thì chữ số thứ 10 có thể nằm trong khoảng từ 0-7.
Vậy, chúng ta cần đảm bảo rằng chữ số thứ 10 không lớn hơn 7. Thực ra với đề bài lần này, chữ số thứ 10 không thể lớn hơn 7, vì giá trị tối đa của kiểu số nguyên 32-bit là 2,147,483,647, tức là chữ số thứ 10 sau khi đảo ngược sẽ chỉ có thể là 1 hoặc 2.
Quan sát tương tự cũng có thể được thực hiện đối với các số âm.
(by ndaadn)
