Hiểu bài toán

Bài toán yêu cầu đếm số lần xuất hiện của một số nguyên x trong một mảng A gồm n phần tử. Input gồm hai dòng: dòng đầu chứa n (số lượng phần tử) và x (giá trị cần tìm), dòng thứ hai chứa n phần tử của mảng. Với ràng buộc n <= 10^6 và giá trị phần tử lên tới 10^9, giải pháp cần xử lý hiệu quả về thời gian và bộ nhớ.

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

Cách Brute Force (Duyệt mảng)

#include <stdio.h>

int main() {
    int n, x;
    scanf("%d%d", &n, &x);
    int a[10000]; // Khai báo mảng với kích thước cố định
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 0; i < n; i++) {
        if (a[i] == x) {
            cnt++;
        }
    }
    printf("%d", cnt);
    return 0;
}

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

Đây là phương pháp cơ bản nhất. Ta lần lượt đọc vào các phần tử của mảng, sau đó duyệt lại toàn bộ mảng một lần nữa để đếm số lần x xuất hiện. Tuy nhiên, giải pháp này không tối ưu bằng cách đếm ngay khi nhập dữ liệu (như Solution 1). Mảng được khai báo với kích thước cố định 10000, có thể gây lỗi phân bổ bộ nhớ nếu n lớn hơn.

Cách Optimized Input Processing (Xử lý nhập liệu tối ưu)

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
int main()
{
    int n, x;
    scanf("%d%d", &n, &x);
    int a[n];
    int cnt = 0;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
        if (a[i] == x)
        {
            ++cnt;
        }
    }
    printf("%d", cnt);
}

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

Đây là cách tiếp cận hiệu quả và phổ biến nhất cho bài toán này. Ta chỉ cần duyệt qua mảng một lần duy nhất ngay khi nhập dữ liệu. Mỗi khi nhập một phần tử, ta so sánh nó với x ngay lập tức và tăng biến đếm nếu khớp. Cách này giúp tiết kiệm thời gian so với việc duyệt lại một vòng lặp riêng biệt. Mảng a[n] được khai báo bằng biến lồng (VLA), an toàn cho bộ nhớ với n <= 10^6 (khoảng 4MB).

Cách Modular Approach (Hàm bổ trợ)

#include <stdio.h>

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

int find_x (int a[], int n, int x) {
    int count = 0;
    for (int i=0; i<n; i++) {
        if (a[i]==x) {
            count ++;
        }
    }
    return count;
}

int main () {
    int n, a[100],x;
    scanf ("%d %d", &n, &x);
    nhap(a,n);
    printf ("%d", find_x(a,n,x));
    return 0;
}

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

Phương pháp này chia chương trình thành các hàm riêng biệt nhap và find_x để code rõ ràng, dễ đọc hơn. Logic vẫn là duyệt qua mảng để đếm. Tuy nhiên, giải pháp này có nhược điểm là khai báo mảng a[100] cố định, dẫn đến sai lỗi nghiêm trọng nếu n > 100. Ngoài ra, nó thực hiện 2 vòng lặp (một để nhập, một để tìm) nên chậm hơn một chút so với cách đếm ngay khi nhập.

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

Bài học kinh nghiệm

• Với ràng buộc n <= 10^6, giải thuật tuyến tính O(n) là bắt buộc.
• Đọc dữ liệu và xử lý đồng thời (đếm ngay khi đọc) giúp tối ưu hóa cả thời gian và mã nguồn.

Lỗi thường gặp

• Khai báo mảng cố định (ví dụ int a[100]) thay vì dùng biến kích thước mảng (VLA) hoặc cấp phát động, dẫn đến tràn bộ nhớ (Stack Overflow hoặc lỗi lỗi Segment Fault) khi n lớn.
• Quên kiểm tra điều kiện đầu vào hoặc lỗi định dạng trong scanf.