Hiểu bài toán

Cho một số nguyên dương n có độ lớn lên đến 10^1000 (quá lớn để lưu trữ trong các kiểu dữ liệu số nguyên thông thường). Yêu cầu viết chương trình in ra số đảo ngược của n. Số đảo ngược được tạo ra bằng cách viết lại các chữ số của n theo thứ tự ngược lại. Ví dụ: đảo ngược của 1234 là 4321. Lưu ý quan trọng: các số 0 ở đầu của số n sẽ trở thành số 0 ở cuối của số đảo ngược, nhưng theo quy ước toán học, số nguyên dương không có chữ số 0 ở đầu. Do đó, cần loại bỏ các số 0 ở cuối của số n (trước khi đảo ngược) để đảm bảo kết quả không có số 0 ở đầu. Ví dụ: đảo ngược của 1320 là 231.

Các cách tiếp cận

Cách Xử lý chuỗi trực tiếp và loại bỏ số 0 ở cuối

#include <stdio.h>
#include <string.h>

int main(){
    char s[1005];
    scanf("%s", s);
    int len = strlen(s);
    int m = len - 1;
    int t = 0;
    // Đếm số lượng số 0 ở cuối chuỗi
    while(s[m] == '0'){
        t++;
        m--;
    }
    // In ngược chuỗi từ ký tự cuối cùng không phải 0 về đầu
    for(int i = len - 1 - t; i >= 0; i--)
        printf("%c", s[i]);
    return 0;
}

• Time Complexity: O(N), với N là độ dài của chuỗi số n
• Space Complexity: O(N) để lưu trữ chuỗi đầu vào

Phương pháp này xử lý số như một chuỗi ký tự. Đầu tiên, chúng ta đếm số lượng số 0 xuất hiện ở cuối chuỗi (chính là các số 0 ở đầu của số đảo ngược). Biến m trỏ đến ký tự cuối cùng không phải là 0. Biến t đếm số lượng số 0 đó. Sau đó, vòng lặp for in ngược chuỗi từ ký tự tại vị trí len - 1 - t (ký tự cuối cùng không phải 0) về đến ký tự đầu tiên. Cách này loại bỏ các số 0 thừa ở đầu kết quả một cách hiệu quả.

Cách Xử lý chuỗi với cờ kiểm tra

#include <stdio.h>
#include <string.h>

int main()
{
  int cnt = 0;
  char a[10000];
  scanf("%s", a);
  cnt = strlen(a);
  int oke = 0; // Cờ kiểm tra đã gặp ký tự khác 0 chưa
  for(int i = cnt - 1; i >= 0; i--){
    if(a[i] != '0'){
      oke = 1; // Kích hoạt cờ khi gặp ký tự khác 0
    }
    if(oke){
      printf("%c", a[i]);
    }
  }
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Phương pháp này cũng duyệt chuỗi từ cuối lên đầu (tương đương với việc duyệt số đảo ngược từ đầu). Nó sử dụng một biến boolean oke để đánh dấu. Khi chưa gặp ký tự khác '0', các ký tự '0' sẽ bị bỏ qua (không in ra). Ngay khi gặp ký tự đầu tiên khác '0', cờ oke được bật và tất cả các ký tự từ đó trở về sau (bao gồm cả các ký tự '0' ở giữa số) đều được in ra. Logic này đảm bảo loại bỏ các số 0 ở đầu kết quả.

Cách Xử lý chuỗi với chỉ số bắt đầu

int main() {
    char c[1000];

    scanf("%s", c);
    int lenght = strlen(c) - 1;
    int cnt = 0;
    while (lenght >= 0){
        if(c[lenght] == '0'){
            ++cnt;
        }
        else if(c[lenght] != '0') break;
        --lenght;
    }

    for(int i = strlen(c) - 1 - cnt; i >=0; --i){
        printf("%c", c[i]);
    }

    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Tương tự như phương pháp 1, cách tiếp cận này đếm số lượng số 0 ở cuối chuỗi bằng cnt. Nó dùng một vòng lặp while để tìm vị trí của ký tự khác 0 đầu tiên tính từ cuối. Sau đó, vòng lặp for in ngược chuỗi từ chỉ số strlen(c) - 1 - cnt về 0. Đây là cách triển khai trực quan của thuật toán loại bỏ số 0 đầu vào.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Vì giới hạn của input lên tới 10^1000, bắt buộc phải xử lý input dưới dạng chuỗi (string) thay vì các kiểu số nguyên (int, long long).
• Bài toán yêu cầu loại bỏ các số 0 ở đầu của kết quả. Số 0 này tương ứng với các số 0 ở cuối của input. Do đó, cần xử lý phần đuôi của chuỗi input trước.
• Có hai cách tiếp cận chính: (1) Đếm số lượng 0 ở cuối rồi in ngược chuỗi (không bao gồm số 0 đã đếm). (2) Duyệt ngược chuỗi và in ra các ký tự chỉ sau khi đã gặp một ký tự khác 0.

Lỗi thường gặp

• In ra các số 0 ở đầu của số đảo ngược: Ví dụ, nếu input là '100', output đúng là '1', nhưng nếu chỉ đơn giản in ngược chuỗi thì sẽ ra '001'.
• Quên xử lý trường hợp input chỉ toàn số 0 (ví dụ '000'): Tuy đề bài giới hạn n > 0, nhưng trong các bài toán khác, trường hợp này có thể gây lỗi nếu không kiểm tra kỹ.
• Sử dụng biến số nguyên để lưu trữ số input: Không thể lưu trữ số có hàng nghìn chữ số vào int hay long long được.