在C ++中对总和小于x的排序数组中的对进行计数

给我们一个排序后的整数类型元素和一个整数变量x的数组,任务是从给定的数组中形成对,并计算该对中元素的总和,并检查计算出的总和是否小于x。

输入− int arr [] = {2,7,1,0,8},int x = 8

输出-总和小于x的排序数组中的对数为-4

说明-可以从给定数组形成的对为:(2,7)= 9(大于x),(2,1)= 3(小于x),(2,0)= 2(小于x) x),(2,8)= 10(大于x),(7,1)= 8(等于x),(7,0)= 7(小于x),(7,8)= 15(大于x),(1,0)= 1(小于x),(1,8)= 8(等于x),(0,8)= 8(等于x)。因此,总和小于x的对为(4,0)和(2,2)。因此,总和小于x的对数为4。

输入− int arr [] = {2,4,6,8},int x = 10

输出-总和小于x的排序数组中的对数为-2

说明-可以从给定数组形成的对为:(2,4)= 6(小于x),(2,6)= 8(小于x),(2,8)= 10(等于x),(4,6)= 10(等于x),(4,8)= 12(大于x),(6,8)= 14(大于x)。因此,总和小于x的对数为2。

以下程序中使用的方法如下

解决给定问题的方法可以有多种,即幼稚方法和有效方法。因此,让我们首先来看一下幼稚的方法

  • 输入一个整数元素数组并计算数组的大小并将数据传递给函数

  • 声明一个临时变量数以存储总和小于x的对数。

  • 从i到0开始循环直到数组大小

  • 在循环内部,从j到i + 1开始另一个循环,直到数组大小

  • 在循环内部,将总和计算为arr [i] + arr [j],并检查IF sum <x,然后将计数加1。

  • 返回计数

  • 打印结果。

高效的方法

  • 输入一个整数元素数组并计算数组的大小并将数据传递给函数

  • 声明一个临时变量数以存储总和小于x的对数。

  • 将arr_0设置为0,并将arr_1设置为size-1

  • 从arr_0到arr_1启动FOR循环

  • 在循环中,检查IF arr [arr_0] + arr [arr_1] <x,然后将count设置为count +(arr_1-arr_0)并将arr_0 ++ ELSE递减arr_1 1

  • 返回计数

  • 打印结果。

示例(幼稚的方法)

#include <iostream>
using namespace std;
int pair_sum(int arr[], int size, int x){
   int count = 0;
   int sum = 0;
   for(int i = 0 ;i <size ; i++){
      for(int j = i+1; j<size; j++){
         sum = arr[i] + arr[j];
         if(sum < x){
            count++;
         }
      }
   }
   return count;
}
int main(){
   int arr[] = {2, 7, 1, 0, 8};
   int size = sizeof(arr) / sizeof(arr[0]);
   int x = 8;
   cout<<"Count of pairs in a sorted array whose sum is less than x are: "<<pair_sum(arr, size, x);
   return 0;
}

输出结果

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

Count of pairs in a sorted array whose sum is less than x are: 4

示例(有效方法)

#include <iostream>
using namespace std;
int pair_sum(int arr[], int size, int x){
   int arr_0 = 0;
   int arr_1 = size-1;
   int count = 0;
   while(arr_0 < arr_1){
      if (arr[arr_0] + arr[arr_1] < x){
         count = count + (arr_1 - arr_0);
         arr_0++;
      }
      else{
         arr_1--;
      }
   }
   return count;
}
int main(){
   int arr[] = {2, 7, 1, 0, 8};
   int size = sizeof(arr) / sizeof(arr[0]);
   int x = 8;
   cout<<"Count of pairs in a sorted array whose sum is less than x are: "<<pair_sum(arr, size, x);
   return 0;
}

输出结果

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

Count of pairs in a sorted array whose sum is less than x are: 4
猜你喜欢