C++で列の合計が行の合計よりも大きいペアの数をカウントします

これを行うには、マトリックスをトラバースし、各行と列の要素の合計を計算します。

それぞれの要素の合計をrowsum[N]に格納し、各列の要素の合計をcolsum[N]に格納します。

次に、rowsum[i]とcolsum[j]のペアを作成し、colsum [j]>rowsum[i]かどうかを確認します。そのようなペアの真の増分カウントの場合。

例を挙げて理解しましょう。

Input-: matrix= {
   { 1,2,0,1},
   { 3,3,0,2},
   { 1,3,0,2},
   { 3,0,0,2} 
};

出力 −有効なペアの数− 9

説明 −

Rowsum[0]= 1+2+0+1=5 Colsum[0]= 1+3+1+3=8
Rowsum[1]=3+3+0+2=8 Colsum[1]= 2+3+3+0=8
Rowsum[2]= 1+3+0+2=6 Colsum[2]= 0+0+0+0=0
Rowsum[3]=3+0+0+2=5 Colsum[3]= 1+2+2+2=7
Pairs of (i,j) such that rowsum[i] < colsum[j].
(0,0), (0,1), (0,3), (2,0), (2,1), (2,3), (3,0) (3,1), (3,3)

入力 −

Arr[]= { {1,1,1}, {1,1,1}, {1,1,1} } N=3

出力 −有効なペアの数− 0

説明 −

Rowsum[0]= 1+1+1=3 Colsum[0]= 1+1+1=3
Rowsum[1]= 1+1+1=3 Colsum[1]= 1+1+1=3
Rowsum[2]= 1+1+1=3 Colsum[2]= 1+1+1=3
No pairs possible where rowsum[i]<colsum[j]

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

• 乱数で初期化された整数配列Arr[]を使用します。

• Arr[]の長さを格納する変数nを取ります。

• 関数countPairs（int arr []、int n）は配列を受け取り、その長さを入力として受け取り、有効で目的の条件を満たすペアを返します。

• 2つの配列rowsum[n]とcolsum[n]を取ります。

• 行列をトラバースし、arr [i][j]をrowsum[i]とcolsum[j]に追加して、行iと列jの合計を計算します。

• 次に、2つのforループを使用して配列colsum[]とrowsum[]をトラバースします。

• colsum [j]>rowsum[i]がある場合。インクリメントカウント。

• 結果としてカウントを返します。

例

#include <bits/stdc++.h>
using namespace std;
int countPairs(int arr[][3], int n){
   // Count of pairs
   int count = 0;
   int rowsum[n]={0};
   int colsum[n]={0};
   int i,j;
   for (i = 0; i < n; i++){
      for (j = 0; j < n; j++){
         rowsum[i]+=arr[i][j];
         colsum[j]+=arr[i][j];
      }
   }
   for(i=0;i<n;i++){
      for(j=0;j<n;j++)
         if(colsum[j]>rowsum[i])
            { count++; }
   }
   return count;
}
int main(){
   int Arr[][3] = { {1,3,5},{2,4,6},{3,5,7} };
   int side=3;
   cout <<endl<<"Count of number of pairs : "<< countPairs(Arr, side);
   return 0;
}

出力

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

Count of number of pairs : 4