Chúng ta được cung cấp một ma trận có kích thước NXN. Mục đích là tìm số lượng tất cả các cặp chỉ mục hợp lệ (i, j) sao cho tổng các phần tử của cột j lớn hơn tổng các phần tử của hàng i.
Chúng tôi sẽ thực hiện việc này bằng cách duyệt qua ma trận và tính tổng các phần tử của mỗi hàng và cột.
Lưu trữ tổng các phần tử của mỗi phần trong rowum [N] và tổng các phần tử của mỗi cột trong colsum [N].
Bây giờ hãy tạo các cặp rowum [i] và colsum [j] và kiểm tra xem colsum [j]> rowsum [i]. Nếu số gia tăng đúng cho các cặp như vậy.
Hãy cùng hiểu với các ví dụ.
Input-: matrix= {
{ 1,2,0,1},
{ 3,3,0,2},
{ 1,3,0,2},
{ 3,0,0,2}
}; Đầu ra - Số lượng các cặp hợp lệ - 9
Giải thích -
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)
Đầu vào -
Arr[]= { {1,1,1}, {1,1,1}, {1,1,1} } N=3 Đầu ra - Số lượng các cặp hợp lệ - 0
Giải thích -
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]
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Chúng tôi lấy một mảng số nguyên Arr [] được khởi tạo với các số ngẫu nhiên.
-
Lấy một biến n lưu trữ độ dài của Arr [].
-
Hàm countPairs (int arr [], int n) nhận một mảng, độ dài của nó làm đầu vào và trả về các cặp hợp lệ và đáp ứng các điều kiện mong muốn.
-
Chúng tôi lấy hai mảng rowum [n] và colsum [n].
-
Ma trận nghịch đảo và thêm arr [i] [j] vào rowum [i] và colsum [j] để tính tổng của hàng i và cột j.
-
Bây giờ hãy duyệt các mảng colsum [] và rowum [] bằng cách sử dụng hai vòng lặp for.
-
Nếu bất kỳ cột nào [j]> rowum [i]. Số lượng tăng dần.
-
Trả về kết quả là số lượng.
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of number of pairs : 4