C++で合計が4で割り切れる配列のペアを数える方法

整数型の要素を含む配列が与えられます。この配列からペアを作成し、各ペアの要素の合計を計算して、その合計が4で割り切れるかどうかを判定するのが課題です。

入力 − int arr[] = {4, 1, 2, 0, 2}

出力 − 合計が4で割り切れるペアの数 − 2

説明 − 与えられた配列から作成できるペアとその合計は次の通りです。(4, 1) = 5（割り切れない）、(4, 2) = 6（割り切れない）、(4, 0) = 4（割り切れる）、(4, 2) = 6（割り切れない）、(1, 2) = 3（割り切れない）、(1, 0) = 1（割り切れない）、(1, 2) = 3（割り切れない）、(2, 0) = 2（割り切れない）、(2, 2) = 4（割り切れる）、(0, 2) = 2（割り切れない）。したがって、合計が4で割り切れるペアは (4, 0) と (2, 2) の2つです。

入力 − int arr[] = {2, 4, 8, 6, 10}

出力 − 合計が4で割り切れるペアの数 − 4

説明 − 作成できるペアのうち、合計が4で割り切れるものは (2, 6) = 8、(2, 10) = 12、(4, 8) = 12、(6, 10) = 16 の4つです。それ以外のペア、たとえば (2, 4) = 6 や (8, 10) = 18 などは4で割り切れません。

プログラムで使用するアプローチ

この問題を解くには、素朴なアプローチ（総当たり法）と効率的なアプローチの複数の方法があります。まずは素朴なアプローチから見ていきましょう。

素朴なアプローチ

• 整数型の要素を持つ配列を入力し、配列のサイズを計算して関数に渡します。

• 合計が4で割り切れるペアの個数を格納するための一時変数 count を宣言します。

• i を 0 から配列のサイズまでループさせます。

• そのループの中で、j を i + 1 から配列のサイズまでネストしたループで回します。

• sum = arr[i] + arr[j] として合計を計算し、sum % 4 == 0 であれば count を1増やします。

• count を返し、結果を出力します。

効率的なアプローチ

• 整数型の要素を持つ配列を入力し、配列のサイズを計算して関数に渡します。

• 合計が4で割り切れるペアの個数を格納するための一時変数 count を宣言します。

• 4で割った余りは 0〜3 の4種類しかないため、サイズ4のカウント用配列 check[] を作成します。

• i を 0 から配列のサイズまでループさせ、temp = arr[i] % 4 として余りを求め、++check[temp] で該当する余りの出現回数をカウントします。

• 余りが0同士のペア数を count = check[0] * (check[0] - 1) / 2 として計算します。

• 余りが2同士のペア数を count += check[2] * (check[2] - 1) / 2 として加算します。

• 余りが1と3の組み合わせのペア数を count += check[1] * check[3] として加算します。

• count を返し、結果を出力します。

この方法が成立する理由は、2つの数の和が4で割り切れるのは、それぞれの数を4で割った余りの組み合わせが (0, 0)、(2, 2)、(1, 3) のいずれかの場合だけだからです。あらかじめ余りごとの個数を数えておけば、すべてのペアを実際に試すことなく、組み合わせの公式で答えを直接求められます。計算量は素朴なアプローチの O(n²) に対し、O(n) まで改善されます。

例（素朴なアプローチ）

#include <iostream>
using namespace std;
int pair_4(int arr[], int size){
   int count = 0;
   for(int i = 0 ;i <size ; i++){
      for(int j = i+1; j<size; j++){
         int sum = arr[i] + arr[j];
         if(sum % 4 == 0){
            count++;
         }
      }
   }
   return count;
}
int main(){
   int arr[] = {4, 1, 2, 0, 2};
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"合計が4で割り切れるペアの数: "<<pair_4(arr, size);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます −

合計が4で割り切れるペアの数: 2

例（効率的なアプローチ）

#include <iostream>
using namespace std;
int pair_4(int arr[], int size){
   int temp = 0;
   int count = 0;
   int check[] = {0, 0, 0, 0};
   for (int i = 0; i < size; i++){
      temp = arr[i] % 4;
      ++check[temp];
   }
   count = check[0] * (check[0] - 1) / 2;
   count = count + check[2] * (check[2] - 1) / 2;
   count = count + check[1] * check[3];
   return count;
}
int main(){
   int arr[] = {4, 1, 2, 0, 2};
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"合計が4で割り切れるペアの数: "<<pair_4(arr, size);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます −

合計が4で割り切れるペアの数: 2

まとめ

素朴なアプローチは二重ループですべてのペアを調べるため、時間計算量は O(n²) ですが実装が簡単です。一方、効率的なアプローチは剰余ごとの出現回数を利用することで時間計算量 O(n)・空間計算量 O(1) で解くことができ、配列のサイズが大きい場合に大きな差となります。