Đếm nhóm kích thước 2 hoặc 3 có tổng chia hết cho 3 trong C++

Trong hướng dẫn này, ta sẽ thảo luận chương trình để tìm số lượng nhóm kích thước 2 hoặc 3 có tổng chia hết cho 3.

Ví dụ

#include <bits/stdc++.h>
using namespace std;

int count_groups(int arr[], int n) {
    int c[3] = {0};
    for(int i = 0; i < n; i++)
        c[arr[i] % 3]++;
    int res = 0;
    // Cặp 2 phần tử
    res += (c[0] * (c[0] - 1)) / 2;  // (0,0)
    res += c[1] * c[2];              // (1,2)
    // Bộ 3 phần tử
    res += (c[0] * (c[0] - 1) * (c[0] - 2)) / 6;  // (0,0,0)
    res += (c[1] * (c[1] - 1) * (c[1] - 2)) / 6;  // (1,1,1)
    res += (c[2] * (c[2] - 1) * (c[2] - 2)) / 6;  // (2,2,2)
    res += c[0] * c[1] * c[2];                    // (0,1,2)
    return res;
}

int main() {
    int arr[] = {3, 6, 7, 2, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Required number of groups are " << count_groups(arr, n) << endl;
    return 0;
}

Kết quả

Required number of groups are 8