在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开始循环直到数组大小

  • 在循环内部,从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;

}

输出结果

如果我们运行上面的代码,它将生成以下输出-

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

以上是 在C ++中计数其和可被K整除的数组中的对 的全部内容, 来源链接: utcz.com/z/348913.html

回到顶部