C++で2つの配列から桁の合計が等しい異なるペアをカウントする方法

2つの整数型配列 arr_1[] と arr_2[] が与えられたとき、「桁の合計(各桁の数字を足し合わせた値)が等しくなる異なるペア」の個数を求めるのがこの記事の課題です。ペアを作る際には、arr_1[] から1つの値を、arr_2[] からもう1つの値を選び、選んだ2つの値の桁の合計が一致していなければなりません。

配列とは、同じ型の要素を固定サイズで連続的に格納できるデータ構造の一種です。データの集合をまとめて扱うために使われますが、「同じ型の変数が並んだ集合」と捉えると、より理解しやすくなります。

具体例

入力 − int arr_1[] = {1, 22, 42, 17}
int arr_2[] = {1, 31, 6, 8}
出力 − count is 4

説明 − 桁の合計が等しいペアは全部で4つあり、それぞれ (1, 1)、(22, 31)、(42, 6)、(17, 8) です。

入力 − int arr_1[] = {1, 22, 42, 17}
int arr_2[] = {2, 78, 6, 18}
出力 − count is 1

説明 − 桁の合計が等しいペアは (42, 6) の1つだけなので、カウントは 1 となります。

入力 − int arr_1[] = {1, 22, 42, 17}
int arr_2[] = {2, 78, 16, 18}
出力 − count is 0

説明 − 桁の合計が一致するペアが存在しないため、カウントは 0 になります。

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

• まず、2つの配列 arr_1[] と arr_2[] を用意します。
• length() 関数を使って、両方の配列の長さ(要素数)を整数値として取得します。
• 重複するペアの登録を避けるため、set 型の変数(例: st)を作成します。
• i を 0 から開始し、i が arr_1[] のサイズ未満である間、外側のループを回します。
• その内側で、j を 0 から開始し、j が arr_2[] のサイズ未満である間、ネストされたループを回します。
• sumdigits(arr_1[i]) と sumdigits(arr_2[j]) が等しい場合、さらに arr_1[i] < arr_2[j] であれば make_pair(arr_1[i], arr_2[j]) をセットに挿入します。
• そうでない場合は make_pair(arr_2[j], arr_1[i]) を挿入します。常に小さい値を先頭にすることで、同じ組み合わせのペアが二重に登録されるのを防げます。
• 最後に st.size() を返し、その結果を出力します。

サンプルコード

#include <iostream>
#include <set>
using namespace std;
// 数値の各桁の合計を求める関数
int sumdigits(int n){
   int sum = 0;
   while (n > 0){
      sum += n % 10;
      n = n / 10;
   }
   return sum;
}
// 桁の合計が等しいペアの個数をカウントする関数
int paircount(int arr_1[], int arr_2[], int size1, int size2){
   // set を使い、重複するペアの登録を防ぐ
   set<pair<int, int> > myset;
   for (int i = 0; i < size1; i++){
      for (int j = 0; j < size2; j++){
         // 両方の要素の桁の合計を比較
         if (sumdigits(arr_1[i]) == sumdigits(arr_2[j])){
            if (arr_1[i] < arr_2[j]){
               myset.insert(make_pair(arr_1[i], arr_2[j]));
            } else{
               myset.insert(make_pair(arr_2[j], arr_1[i]));
            }
         }
      }
   }
   // セットのサイズ(= 異なるペアの個数)を返す
   return myset.size();
}
// ドライバーコード
int main(){
   int arr_1[] = { 1, 22, 42, 17 };
   int arr_2[] = { 5, 31, 6, 8 };
   int size1 = sizeof(arr_1) / sizeof(arr_1[0]);
   int size2 = sizeof(arr_2) / sizeof(arr_2[0]);
   cout <<"count is "<<paircount(arr_1, arr_2, size1, size2);
   return 0;
}

出力

上記のコードを実行すると、次のような出力が得られます −

count is 3

計算量について

このアルゴリズムは2重ループを使用するため、時間計算量は O(n × m)(n と m はそれぞれの配列のサイズ)になります。また、セットに保存されるペアの数に依存し、空間計算量も最大で O(n × m) です。配列のサイズが大きいケースでは、あらかじめ各要素の桁の合計を計算してハッシュマップで出現数を管理する方式に置き換えることで、処理効率を大きく改善できます。