Editorial for frienum: Số có bạn

Hiểu bài toán

Bài toán yêu cầu đếm số lượng các phần tử trong mảng xuất hiện nhiều hơn một lần (gọi là 'số có bạn'). Với mỗi số xuất hiện k lần (k >= 2), tất cả k phần tử đó đều được tính vào kết quả. Ví dụ: mảng [1, 2, 2, 3, 1, 2] có số 1 xuất hiện 2 lần, số 2 xuất hiện 3 lần. Tổng số lượng số có bạn là 2 + 3 = 5.

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

Cách Sử dụng mảng đánh dấu (Frequency Array)

#include <stdio.h>
#include <stdlib.h>

#define MAX 1000001

int main() {
    int n;
    scanf("%d", &n);

    // Khởi tạo mảng đếm tần suất với giá trị 0
    int *count = (int*)calloc(MAX, sizeof(int));

    // Đọc dữ liệu và đếm tần suất
    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        count[x]++;
    }

    int result = 0;
    // Duyệt qua mảng tần suất để tính tổng
    for (int i = 0; i < MAX; i++) {
        if (count[i] > 1) {
            result += count[i];
        }
    }

    printf("%d", result);
    free(count);
    return 0;
}

• Time Complexity: O(n + M) ~ O(n) (với M là giá trị tối đa của a_i)
• Space Complexity: O(M) ~ O(10^6)

Phương pháp này sử dụng một mảng phụ (mảng tần suất) với kích thước cố định (ví dụ 1,000,001) để lưu số lần xuất hiện của mỗi số. Ta duyệt qua mảng đầu vào, với mỗi phần tử a[i], ta tăng count[a[i]] lên 1. Sau đó, ta duyệt qua mảng count, nếu count[i] > 1, ta cộng dồn count[i] vào kết quả. Đây là cách tiếp cận hiệu quả nhất về mặt thời gian cho các giới hạn giá trị a_i nhỏ.

Cách Một lần duyệt với mảng đánh dấu

#include <stdio.h>
#include <stdlib.h>

#define MAX 1000001

int main() {
    int n;
    scanf("%d", &n);

    // Mảng count để đếm, mảng counted để đánh dấu đã tính vào kết quả chưa
    int *count = (int*)calloc(MAX, sizeof(int));
    int *counted = (int*)calloc(MAX, sizeof(int));

    // Lưu các số vào mảng a để xử lý sau
    int *a = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        count[a[i]]++;
    }

    int result = 0;
    for (int i = 0; i < n; i++) {
        // Chỉ cộng dồn khi số lần xuất hiện >= 2 và chưa từng được cộng trước đó
        if (count[a[i]] >= 2 && counted[a[i]] == 0) {
            result += count[a[i]];
            counted[a[i]] = 1; // Đánh dấu đã tính
        }
    }

    printf("%d", result);
    free(count);
    free(counted);
    free(a);
    return 0;
}

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

Đây là biến thể của giải pháp mảng tần suất. Thay vì duyệt lại toàn bộ mảng tần suất (vòng lặp từ 0 đến M), giải pháp này chỉ duyệt qua các phần tử đã nhập. Bước 1: Đếm tần suất. Bước 2: Duyệt lại mảng a, nếu một số có tần suất >= 2 và chưa được xử lý, cộng tần suất đó vào kết quả và đánh dấu đã xử lý. Cách này giúp tiết kiệm thời gian nếu M rất lớn nhưng n nhỏ.

Cách Thứ tự hóa mảng (Sorting)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    sort(a.begin(), a.end());

    int result = 0;
    int i = 0;
    while (i < n) {
        int j = i + 1;
        // Tìm phần tử khác đầu tiên
        while (j < n && a[j] == a[i]) {
            j++;
        }

        // Nếu j > i + 1, tức là có ít nhất 2 phần tử giống nhau
        if (j - i > 1) {
            result += (j - i);
        }
        i = j;
    }

    cout << result;
    return 0;
}

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

Giải pháp này không dùng mảng tần suất mà sắp xếp mảng tăng dần. Các phần tử giống nhau sẽ đứng cạnh nhau. Ta chỉ cần duyệt một lần để đếm độ dài của các đoạn gồm các số giống nhau. Nếu độ dài >= 2, cộng vào kết quả. Cách này có độ phức tạp thời gian cao hơn (do sắp xếp) nhưng không phụ thuộc vào giá trị tối đa của ai, phù hợp khi ai có thể rất lớn.

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

Bài học kinh nghiệm

• Bài toán có thể được giải quyết bằng cách đếm tần suất của từng số.
• Với giới hạn a_i <= 10^6, việc sử dụng mảng tần suất (Frequency Array) là tối ưu nhất về thời gian O(n).
• Nếu dùng mảng tần suất, ta có thể cộng dồn kết quả ngay khi duyệt mảng hoặc duyệt lại mảng tần suất sau khi đã đếm xong.

Lỗi thường gặp

• Sử dụng map (cây đỏ-đen) thay cho mảng tần suất có thể làm chậm chương trình do chi phí thường truy cập lớn hơn, dù độ phức tạp lý thuyết vẫn là O(n log n).
• Quên kiểm tra điều kiện tần suất >= 2 trước khi cộng vào kết quả.
• Lỗi cấp phát bộ nhớ nếu dùng mảng c cục bộ quá lớn (nên dùng cấp phát động calloc/malloc).