Editorial for xornary: Phép XOR trên dãy nhị phân

Hiểu bài toán

Bài toán yêu cầu thực hiện phép toán XOR bit-wise trên hai chuỗi nhị phân A và B có cùng độ dài. Kết quả là một chuỗi nhị phân mới, trong đó mỗi bit là kết quả của phép XOR giữa các bit tương ứng của A và B. Yêu cầu quan trọng là phải loại bỏ các ký tự '0' đứng đầu trong kết quả. Ví dụ: nếu kết quả là '0101', ta chỉ in ra '101'.

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

Cách Xử lý từng ký tự với cờ kiểm tra (Output Streaming)

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

int main(){
    char a[1000],b[1000];
    scanf("%s",a);
    scanf("%s",b);
    int p = strlen(a);
    int res = 0;
    for (int i = 0; i < p; i++){
        int c = a[i] - '0';
        int d = b[i] - '0';
        if (c ^ d == 0 && !res) continue;
        printf("%d",c ^ d);
        res = 1;
    }
    return 0;
}

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

Hàm main đọc hai chuỗi a và b. Biến res đóng vai trò là cờ để kiểm tra xem đã in ra ký tự khác '0' lần đầu tiên chưa. Trong vòng lặp for, phép XOR được tính toán. Nếu kết quả XOR là 0 và cờ res chưa được bật (tức là chưa có ký tự nào khác '0' được in ra), vòng lặp sẽ continue để bỏ qua. Khi gặp ký tự '1' đầu tiên, cờ res được bật lên, và các ký tự sau đó (kể cả '0') đều được in ra.

Cách Xử lý từng ký tự với cờ kiểm tra (Mô phỏng logic)

#include<stdio.h>
#include<string.h>
int main(){
    char a[55], b[55];
    scanf("%s %s", a, b);
    int n=strlen(a), dk=0;
    for(int i=0; i<n; i++){
        if(a[i]!=b[i]) dk=1;
        if(dk==1){
            if(a[i]!=b[i]) printf("1");
            else printf("0");
        }
    }
}

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

Cách tiếp cận này sử dụng biến dk (đánh dấu) tương tự như res trong giải pháp 1. Logic kiểm tra a[i] != b[i] được thực hiện hai lần: một lần để bật cờ dk và một lần bên trong if (dk==1) để quyết định in '1' hay '0'. Biến n được tính toán trước để tránh việc lặp lại tính toán strlen trong mỗi bước lặp.

Cách Xử lý mảng trung gian và loại bỏ số 0 đầu

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

int main()
{
    char a[51];
    char b[51];
    scanf("%s %s", a, b);
    int la = strlen(a);
    int lb = strlen(b);
    int maxlen = la > lb ? la : lb;
    char result[maxlen + 1];
    result[maxlen] = '\0';
    for (int i = 0; i < maxlen; i++)
    {
        if (a[i] == b[i])
        {
            result[i] = '0';
        }
        else if (a[i] != b[i])
        {
            result[i] = '1';
        }
    }
    int k = 0;
    while (result[k] == '0')
    {
        k++;
    }
    for (int i = k; i < maxlen; i++)
    {
        printf("%c", result[i]);
    }
    return 0;
}

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

Giải pháp này thực hiện thành 3 bước rõ ràng:

1. Tạo một mảng result để lưu kết quả XOR giữa hai chuỗi.
2. Tìm chỉ số k của phần tử đầu tiên khác '0' trong result.
3. In ra các ký tự từ chỉ số k trở đi. Cách này tốn bộ nhớ hơn do lưu trữ mảng kết quả trung gian, nhưng logic khá rõ ràng và dễ hiểu.

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

Bài học kinh nghiệm

• Phép XOR giữa hai bit giống nhau cho kết quả 0, khác nhau cho kết quả 1.
• Để loại bỏ số 0 đứng đầu, ta cần lặp cho đến khi gặp ký tự '1' đầu tiên, sau đó mới in các ký tự tiếp theo.

Lỗi thường gặp

• Quên kiểm tra trường hợp kết quả toàn số 0 (ví dụ: XOR giữa '101' và '101'). Nếu chỉ dùng vòng lặp bình thường, có thể không in ra gì, hoặc in ra một ký tự rác nếu không xử lý kỹ.
• Sử dụng strlen bên trong điều kiện vòng lặp for (ví dụ: i < strlen(a)). Điều này làm strlen được gọi lại ở mỗi bước lặp, gây giảm hiệu năng.