合計がC++でKで割り切れる配列のペアをカウントします

整数型要素の配列が与えられ、タスクは、与えられた配列からペアを形成し、ペアの要素の合計を計算し、与えられた合計がkで割り切れるかどうかを確認することです。

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

出力 −合計がkで割り切れる配列内のカウントペアは− 2

説明 −指定された配列から形成できるペアは次のとおりです。（4、1）=5（2で割り切れない）、（4、2）=6（2で割り切れる）、（4、0）=4（で割り切れる2）、（1、2）=3（2で割り切れない）、（1、0）=1（2で割り切れない）、（2、0）=2（2で割り切れない）、（2、2）=4（2で割り切れる）、（0、2）=2（2で割り切れる）。したがって、合計をkで割り切れる2のペアは、（4、2）、（4、0）、（2、0）、（2、2）、および（0、2）です。

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

出力 −合計がkで割り切れる配列内のカウントペアは− 4

説明 −指定された配列から形成できるペアは次のとおりです。（2、4）=6（4で割り切れない）、（2、8）=10（4で割り切れない）、（2、6）=8（割り切れる4で割り切れる）、（2、10）=12（4で割り切れる）、（4、8）=12（4で割り切れる）、（4、6）=10（4で割り切れない）、（4、10）=14（4で割り切れない）、（8、6）=14（4で割り切れない）、（8、10）=18（4で割り切れない）、（6、10）=16（4で割り切れない）。したがって、合計が4で割り切れるペアは、（2、10）、（2、6）、（4、8）、および（6、10）です。

以下のプログラムで使用されているアプローチは次のとおりです

与えられた問題を解決するための複数のアプローチ、すなわちナイーブなアプローチと効率的なアプローチがあります。それでは、最初にナイーブなアプローチを見てみましょう。 。

• 整数要素の配列と整数変数をkとして入力し、配列のサイズを計算して、データを関数に渡します

• 一時変数のカウントを宣言して、合計がkで割り切れるペアのカウントを格納します。

• 配列のサイズまでiから0までのループFORを開始します

• ループ内で、配列のサイズになるまで、jからi+1までの別のループFORを開始します

• ループ内で、合計をarr [i] + arr [j]として計算し、IF合計％k ==0を確認してから、カウントを1ずつインクリメントします。

• カウントを返す

• 結果を印刷します。

効率的なアプローチ

• 整数要素の配列を入力し、配列のサイズを計算して、データを関数に渡します

• 一時変数のカウントを宣言して、合計がkで割り切れるペアのカウントを格納します。

• kによる除算性をチェックする必要があるため、サイズkの配列を作成します。

• 配列のサイズまでiから0までのループFORを開始します

• ループ内で、tempをarr [i]％kに設定し、配列を++ check [temp]

  として事前にインクリメントします。

• countをnew_arr[0]*（new_arr [0]-1）/ 2

  として設定します

• i <=k / 2 AND i！=（k-i）

  になるまで、ループFORをiから1として開始します。

• ループ内で、countをcount + new_arr [i] *（new_arr [k --i]）

  として設定します。

• IF k％2 =0を確認し、カウントをカウント+（new_arr [k / 2] *（new_arr [k / 2]-1）/ 2）として設定します

• カウントを返す

• 結果を印刷します。

例（素朴なアプローチ）

#include <iostream>
using namespace std;
int pair_k(int arr[], int size, int k){
   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 % k == 0){
            count++;
         }
      }
   }
   return count;
}
int main(){
   int arr[] = {4, 1, 2, 0, 2};
   int size = sizeof(arr) / sizeof(arr[0]);
   int k = 2;
   cout<<"Count pairs in array whose sum is divisible by 4 are: "<<pair_k(arr, size, k);
   return 0;
}

出力

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

Count pairs in array whose sum is divisible by k are: 6

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

#include <iostream>
using namespace std;
int pair_k(int arr[], int size, int k){
   int temp = 0;
   int count = 0;
   int check[k] = {0};
   for (int i = 0; i < size; i++){
      temp = arr[i] % k;
      ++check[temp];
   }
   count = check[0] * (check[0] - 1) / 2;
   for (int i = 1; i <= k / 2 && i != (k - i); i++){
      count = count + check[i] * (check[k - i]);
   }
   if (k % 2 == 0){
      count = count + (check[k / 2] * (check[k / 2] - 1) / 2);
   }
   return count;
}
int main(){
   int arr[] = {4, 1, 2, 0, 2};
   int size = sizeof(arr) / sizeof(arr[0]);
   int k = 2;
   cout<<"Count pairs in array whose sum is divisible by 4 are: "<<pair_k(arr, size, k);
   return 0;
}

出力

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

Count pairs in array whose sum is divisible by k are: 6