C++で積が​​k未満であるソートされた配列のペアをカウントします

整数型要素と整数変数xのソートされた配列が与えられ、タスクは、与えられた配列からペアを形成し、ペアの要素の積を計算し、計算された積がk未満かどうかを確認することです。

入力

int arr[] = {2, 7, 1, 0, 8}, int k = 10

出力

Count of pairs in a sorted array whose product is less than k are: 7

説明

The pairs that can be formed from the given array are: (2, 7) = 14(greater than k), (2, 1) = 2(less than k), (2, 0) = 0(less than k), (2, 8) = 16(greater than k), (7, 1) = 7(less than k), (7, 0) = 0(less than k), (7, 8) = 56(greater than k), (1, 0) = 0(less than k), (1, 8) = 8(less than k), (0, 8) = 0(less than k). So, the count of pairs with sum less than k are 7.

入力

int arr[] = {2, 4, 6, 8}, int k = 10

出力

Count of pairs in a sorted array whose product is less than k are: 1

説明

The pairs that can be formed from the given array are: (2, 4) = 8(less than k), (2, 6) = 12(greater than k), (2, 8) = 16(greater than k), (4, 6) = 24(greater than x), (4, 8) = 32(greater than k), (6, 8) = 48(greater than k). So, the count of pairs with products less than k is 1.

以下のプログラムで使用されているアプローチは次のとおりです

与えられた問題を解決するための複数のアプローチ、すなわちナイーブなアプローチと効率的なアプローチがあります。それでは、最初にナイーブなアプローチを見てみましょう。 。

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

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

• 配列のサイズまで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_product(int arr[], int size, int k){
   int count = 0;
   int product = 1;
   for(int i = 0 ; i<size ; i++){
      for(int j = i+1; j<size; j++){
         product = arr[i] * arr[j];
         if(product < k){
            count++;
         }
      }
   }
   return count;
}
int main(){
   int arr[] = {5, 8, 2, 1, 3};
   int size = sizeof(arr) / sizeof(arr[0]);
   int k = 10;
   cout<<"Count of pairs in a sorted array whose product is less than k are: "<<pair_product(arr, size, k);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Count of pairs in a sorted array whose product is less than k are: 5

例（効率的なアプローチ）

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

出力

上記のコードを実行すると、次の出力が生成されます-

Count of pairs in a sorted array whose product is less than k are: 10