在C ++中计数其和可被K整除的数组中的对

Z时代
2024-01-10
分类：综合

我们给了一个整数类型的元素数组，任务是从给定的数组中形成对，并计算该对中的元素之和，并检查给定的和是否可被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开始循环直到数组大小
在循环内部，从j到i + 1开始另一个循环，直到数组大小
在循环内部，将总和计算为arr [i] + arr [j]，并检查IF sum％k == 0，然后将计数加1。
返回计数
打印结果。

高效的方法

输入一个整数元素数组并计算数组的大小并将数据传递给函数
声明一个临时变量计数，以存储成对的计数，其和可被k整除。
创建大小为k的数组，因为我们必须检查k的可除性。
从i到0开始循环直到数组大小
在循环内，将temp设置为arr [i]％k，并将数组预递增为++ check [temp]
将计数设置为new_arr [0] *（new_arr [0]-1）/ 2
从i到1开始循环，直到i <= k / 2并且i！=(ki)
在循环内部，将count设置为count + new_arr [i] *（new_arr [k-i]）
检查IF k％2 = 0，然后将count设置为count +（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;
}