C++で合計が3の倍数になるサイズ2・3のグループ数を数える方法

問題概要

数値の配列が与えられたとき、要素の合計が3で割り切れるような「サイズ2」および「サイズ3」のグループがいくつあるかを求める問題です。すべての2つの要素の組み合わせ、および3つの要素の組み合わせについて合計を計算し、それが3で割り切れるかどうかを順番に確認していきます。

具体的な例を見てみましょう。

入力

arr = [1, 2, 3, 4]

出力

4

この例では、合計が3で割り切れる組み合わせが4つ存在します。該当する組み合わせは以下の通りです。

[1, 2]
[2, 4]
[1, 2, 3]
[2, 3, 4]

アルゴリズム

• 配列を初期化します。

• 二重ループを用いて、サイズ2のすべての組み合わせを列挙します。

  • 各グループの合計値を計算します。

  • 合計が3で割り切れる場合は、カウントを1つ増やします。

• 三重ループを用いて、サイズ3のすべての組み合わせを列挙します。

  • 各グループの合計値を計算します。

  • 合計が3で割り切れる場合は、カウントを1つ増やします。

• 最終的なカウントを返します。

実装

以下は、上記のアルゴリズムをC++で実装したコードです。

#include <bits/stdc++.h>
using namespace std;
int getNumberOfGroupsDivisibleBy3(int arr[], int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int sum = arr[i] + arr[j];
            if (sum % 3 == 0) {
                count += 1;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                int sum = arr[i] + arr[j] + arr[k];
                if (sum % 3 == 0) {
                    count += 1;
                }
            }
        }
    }
    return count;
}
int main() {
    int arr[] = { 2, 3, 4, 5, 6, 1, 2, 4, 7, 8 };
    int n = 10;
    cout << getNumberOfGroupsDivisibleBy3(arr, n) << endl;
    return 0;
}

出力

上記のコードを実行すると、次の結果が出力されます。

57

計算量と補足

この方法は考えられるすべての組み合わせを網羅的に調べるため、時間計算量はO(n³)となります。そのため、配列のサイズが大きくなるほど処理時間が増加する点に注意が必要です。

なお、各要素を3で割った余り(0、1、2)ごとに出現回数を数え、その組み合わせから条件を満たすグループ数を導き出せば、より効率的なO(n)の解法も可能です。競技プログラミングなどで大きな入力を扱う場合は、こちらのアプローチを検討するとよいでしょう。