Hiểu bài toán

Bài toán yêu cầu đọc 11 số nguyên từ bàn phím. 10 số đầu tiên được lưu vào một mảng. Số thứ 11 là số cần kiểm tra. Nhiệm vụ là tìm tất cả các vị trí (tính từ 1) trong mảng 10 phần tử mà số thứ 11 xuất hiện. Nếu số đó không t tồn tại trong mảng, in ra -1. Ví dụ: input 1 2 3 4 5 6 7 8 9 1 1, số thứ 11 là 1. Trong mảng [1, 2, 3, 4, 5, 6, 7, 8, 9, 1], số 1 xuất hiện tại vị trí 1 và 10 -> Output: 1 10.

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

Cách Đọc và xử lý trực tiếp (Trộn lẫn nhập và xuất)

#include <stdio.h>

int main() {
    int a[10];
    int found = 0;
    int x;

    // Đọc 10 số đầu vào mảng
    for (int i = 0; i < 10; i++) {
        scanf("%d", &a[i]);
    }

    // Đọc số thứ 11
    scanf("%d", &x);

    // Duyệt mảng để tìm số x
    for (int i = 0; i < 10; i++) {
        if (a[i] == x) {
            printf("%d ", i + 1);
            found = 1;
        }
    }

    if (!found) {
        printf("-1");
    }

    return 0;
}

• Time Complexity: O(1) (vì mảng có cố định 10 phần tử, độ phức tạp không đổi)
• Space Complexity: O(1) (chỉ cần mảng 10 phần tử)

Đây là cách tiếp cận đơn giản nhất và đúng chuẩn nhất. Ta khai báo một mảng 10 phần tử. Vòng lặp đầu tiên đọc 10 số và lưu vào mảng. Vòng lặp thứ hai đọc số thứ 11. Cuối cùng, dùng một vòng lặp duyệt qua mảng để so sánh từng phần tử với số thứ 11. Nếu khớp, in ra vị trí (i+1). Nếu sau vòng lặp biến found vẫn bằng 0, in ra -1.

Cách Xử lý trong một vòng lặp (Một lần duyệt)

#include <stdio.h>

int main() {
    int a[10];
    int x;
    int found = 0;

    // Đọc 11 số, xử lý ngay khi đọc
    for (int i = 0; i < 11; i++) {
        scanf("%d", &x);

        if (i < 10) {
            a[i] = x; // Lưu 10 số đầu vào mảng
        } else {
            // Đã đọc đủ 10 số, x bây giờ là số thứ 11
            // Kiểm tra mảng
            for (int j = 0; j < 10; j++) {
                if (a[j] == x) {
                    printf("%d ", j + 1);
                    found = 1;
                }
            }
        }
    }

    if (!found) {
        printf("-1");
    }

    return 0;
}

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

Phương pháp này gom việc đọc dữ liệu vào một vòng lặp duy nhất. Trong khi duyệt, nếu chỉ số nhỏ hơn 10, ta lưu giá trị vào mảng. Khi chỉ số bằng 10 (phần tử thứ 11), ta sử dụng giá trị vừa đọc được để so sánh với 10 phần tử đã lưu trước đó. Cách này có thể tiết kiệm một dòng lệnh khai báo biến bên ngoài nhưng logic phức tạp hơn một chút.

Cách Sử dụng mảng động (Dynamic Array) - Lỗi logic

#include <stdio.h>
#include <stdbool.h>

int main() {
    // Code này dựa trên Solution 2 nhưng có lỗi logic
    int a[11]; // Mảng 11 phần tử
    int value;

    for (int i = 0; i < 11; i++) {
        scanf("%d", &a[i]);
    }

    value = a[10]; // Lấy giá trị cuối cùng
    bool kt = false;

    // Duyệt từ 0 đến 9 (chỉ xét 10 số đầu)
    for (int i = 0; i < 10; i++) {
        if (a[i] == value) {
            printf("%d ", i + 1);
            kt = true;
        }
    }

    if (!kt) printf("-1");
    return 0;
}

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

Approach này (dựa trên Solution 2 trong bài mẫu) khai báo mảng lớn hơn 10. Tuy nhiên, Solution 2 gốc lại duyệt cả 11 phần tử (i < 11), dẫn đến việc nếu số thứ 11 trùng với 1 trong 10 số đầu thì nó sẽ in ra vị trí 11 (nếu xét a[10]) hoặc sai logic nếu khai báo mảng 100 nhưng chỉ dùng 11 phần tử. Phiên bản sửa lỗi ở trên chỉ duyệt 10 phần tử đầu để đảm bảo đúng yêu cầu bài toán. Tuy nhiên, về cơ bản, đây là cách tiếp cận thừa thãi bộ nhớ so với hai cách trên.

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

Bài học kinh nghiệm

• Bài toán chỉ yêu cầu kiểm tra mảng 10 phần tử cố định, không cần cấu trúc dữ liệu phức tạp.
• Vị trí trong mảng bắt đầu từ 0 (C/C++) nhưng đầu ra yêu cầu từ 1, nên khi in cần cộng thêm 1 vào chỉ số.

Lỗi thường gặp

• Lỗi Logic Vòng lặp: Một số code (như Solution 2) duyệt vòng lặp sai số lượng phần tử (duyệt 11 phần tử của mảng nhưng chỉ có 10 phần tử cần kiểm tra), dẫn đến in ra vị trí 11 hoặc lỗi truy cập ngoài biên.
• Lỗi Kiểu Dữ liệu: Problem Statement cho phép giá trị tuyệt đối lên tới 10^9. Nếu dùng int trong C/C++ (ngưỡng ~2.14x10^9) thì vừa đủ, nhưng nếu dùng unsigned int hoặc xử lý sai dấu thì sẽ bị overflow. Solution 2 dùng long long là cách an toàn nhất.