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より小さい） ）、（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までのループFORを開始します

• ループ内で、配列のサイズになるまで、jからi+1までの別のループFORを開始します

• ループ内で、合計をarr [i] + arr [j]として計算し、IF合計

• カウントを返す

• 結果を印刷します。

効率的なアプローチ

• 整数要素の配列を入力し、配列のサイズを計算して、データを関数に渡します

• 一時変数カウントを宣言して、合計がx未満のペアのカウントを格納します。

• arr_0を0に設定し、arr_1をサイズ-1に設定します

• arr_0からarr_1までのループFORを開始します

• ループ内で、IF arr [arr_0] + arr [arr_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