C++でKで割り切れる合計ペアの数を最大化します

タスクが与えられた場合、Kで割り切れるペアarr [i] +arr[j]の最大数を計算することです。ここでarr[]はN個の整数を含む配列です。

特定のインデックス番号を複数のペアで使用できないという条件があります。

入力

arr[]={1, 2 ,5 ,8 ,3 }, K=2

出力

2

説明 −必要なペアは次のとおりです。（0,2）、（1,3）as 1 + 5=6および2+8=10。 6と10はどちらも2で割り切れます。

代替の答えは、（0,4）、（1,3）または（2,4）、（1,3）のペアである可能性がありますが、答えは同じままです。つまり、2です。

入力

arr[]={1 ,3 ,5 ,2 ,3 ,4 }, K=3

出力

3

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

• int型の変数nに、配列のサイズを格納します

• 関数MaxPairs（）で、順序付けされていないマップを使用し、配列の要素ごとにum [arr [i]％K]として値を1ずつ増やします。

• 繰り返して、可能なすべてのum値を取得します。

• um値がゼロの場合、ペアの数はum [0]/2になります。

• 次に、最小値（um [a]、um [Ka]）

  を使用して、すべてのum値「a」からペアを形成できます。

• 使用されたペアの数であるum値から減算します。

例

#include <bits/stdc++.h>
using namespace std;
int MaxPairs(int arr[], int size, int K){
   unordered_map<int, int> um;
   for (int i = 0; i < size; i++){
      um[arr[i] % K]++;
   }
   int count = 0;
   /*Iteration for all the number that are less than the hash value*/
   for (auto it : um){
      // If the number is 0
      if (it.first == 0){
         //Taking half since same number
         count += it.second / 2;
         if (it.first % 2 == 0){
            um[it.first] = 0;
         }
         else{
            um[it.first] = 1;
         }
      }
      else{
         int first = it.first;
         int second = K - it.first;
         // Check for minimal occurrence
         if (um[first] < um[second]){
            //Taking the minimal
            count += um[first];
            //Subtracting the used pairs
            um[second] -= um[first];
            um[first] = 0;
         }
         else if (um[first] > um[second]){
            // Taking the minimal
            count += um[second];
            //Subtracting the used pairs
            um[first] -= um[second];
            um[second] = 0;
         }
         else{
            //Checking if the numbers are same
            if (first == second){
               //If same then number of pairs will be half
               count += it.second / 2;
               //Checking for remaining
               if (it.first % 2 == 0)
                  um[it.first] = 0;
               else
                  um[it.first] = 1;
            }
            else{
               //Storing the number of pairs
               count += um[first];
               um[first] = 0;
               um[second] = 0;
            }
         }
      }
   }
   return count;
}
//Main function
int main(){
   int arr[] = { 3, 6, 7, 9, 4, 4, 10 };
   int size = sizeof(arr) / sizeof(arr[0]);
   int K = 2;
   cout<<"Maximize the number of sum pairs which are divisible by K is: "<<MaxPairs(arr, size, K);
   return 0;
}

出力

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

Maximize the number of sum pairs which are divisible by K is: 3