最大化C ++中可被K整除的和对的数量

给定任务是计算可被K整除的最大对数arr [i] + arr [j]，其中arr []是包含N个整数的数组。

给定一个特定的索引号不能用于多于一对的条件。

输入值

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

输出结果 

2

说明-所需的对为：(0,2)，(1,3)为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){
      //如果数字为0-
      if (it.first == 0){
         //由于相同的数字取一半
         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;
         //检查最少出现
         if (um[first] < um[second]){
            //以最小
            count += um[first];
            //减去使用过的对
            um[second] -= um[first];
            um[first] = 0;
         }
         else if (um[first] > um[second]){
            // 以最小
            count += um[second];
            //减去使用过的对
            um[first] -= um[second];
            um[second] = 0;
         }
         else{
            //检查数字是否相同
            if (first == second){
               //如果相同，则对数将为一半
               count += it.second / 2;
               //检查剩余
               if (it.first % 2 == 0)
                  um[it.first] = 0;
               else
                  um[it.first] = 1;
            }
            else{
               //存储对数
               count += um[first];
               um[first] = 0;
               um[second] = 0;
            }
         }
      }
   }
   return count;
}
//主要功能
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