हमें NXN आकार का मैट्रिक्स दिया गया है। लक्ष्य इंडेक्स (i,j) के सभी मान्य युग्मों की गिनती इस प्रकार ज्ञात करना है कि कॉलम j का योग तत्व पंक्ति i के तत्वों के योग से अधिक हो।
हम मैट्रिक्स को पार करके ऐसा करेंगे और प्रत्येक पंक्ति और स्तंभ के तत्वों के योग की गणना करेंगे।
पंक्तियों में प्रत्येक के तत्वों का योग [N] और प्रत्येक स्तंभ के तत्वों का योग colsum[N] में संग्रहीत करें।
अब रोसम [i] और कोलसम [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[] यादृच्छिक संख्याओं के साथ आरंभ किया गया।
-
एक वैरिएबल n लें जो Arr[] की लंबाई को स्टोर करता है।
-
फंक्शन काउंटपेयर्स (int arr[], int n) एक ऐरे लेता है, इसकी लंबाई इनपुट के रूप में और उन युग्मों को लौटाता है जो मान्य हैं और वांछित शर्तों को पूरा करते हैं।
-
हम दो सरणियाँ लेते हैं rowsum[n] और colsum[n].
-
ट्रैवर्स मैट्रिक्स और पंक्ति i और कॉलम j के योग की गणना करने के लिए arr[i][j] को rowsum[i] और colsum[j] में जोड़ें।
-
अब दो फॉर लूप्स का उपयोग करके ट्रैवर्स एरेज़ कोलसम [] और रोसम []।
-
यदि कोई 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