Given a matrix of size NxN. The task is to count the number of pair of indices (i, j) such that the sum of j-th column is greater than the sum of i-th row.
Examples:
Input : N = 2, mat[][] = {{1, 2},
{3, 4}}
Output : 2
The 2 valid pairs are (1, 1) and (1, 2).
Input : N = 3, mat[][] = { { 1, 2, 3 },
{ 4, 5, 6 },
{ 7, 8, 9 } };
Output : 4
Approach:
The idea is to pre-calculate the row sum and column sum for each row and column respectively and then count the number of possible valid pairs (i,j) such that column sum of j-th column is greater than the row sum for i-th row.
Below is the implementation of the above approach:
C++
// C++ program to count the number of pairs// (i,j) such that sum of elements in j-th column// is greater than sum of elements in i-th row#include <bits/stdc++.h>using namespace std;#define N 3// Function to count the number of pairs// (i,j) such that sum of elements in j-th column// is greater than sum of elements in i-th rowint countPairs(int a[N][N]){ // Initialize row sum and column // sum to zero int sumr[N] = { 0 }, sumc[N] = { 0 }; // Calculate row sum and column sum for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) { sumr[i] += a[i][j]; sumc[j] += a[i][j]; } int count = 0; // Count the number of pairs that are valid for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) if (sumc[i] > sumr[j]) count++; return count;}// Driver Codeint main(){ int a[][N] = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }; cout << countPairs(a); return 0;} |
Java
// Java program to count the number of pairs// (i,j) such that sum of elements in j-th column// is greater than sum of elements in i-th rowimport java.io.*;class GFG{ static int N = 3;// Function to count the number of pairs// (i,j) such that sum of elements in j-th column// is greater than sum of elements in i-th rowstatic int countPairs(int a[][]){ // Initialize row sum and column // sum to zero int sumr[] = new int[N] ; int sumc[] = new int [N] ; // Calculate row sum and column sum for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) { sumr[i] += a[i][j]; sumc[j] += a[i][j]; } int count = 0; // Count the number of pairs that are valid for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) if (sumc[i] > sumr[j]) count++; return count;} // Driver Code public static void main (String[] args) { int a[][] = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }; System.out.println (countPairs(a)); }}// This code is contributed by jit_t. |
Python3
# Python 3 program to count the number of pairs# (i,j) such that sum of elements in j-th column# is greater than sum of elements in i-th rowN = 3# Function to count the number of pairs# (i,j) such that sum of elements in j-th column# is greater than sum of elements in i-th rowdef countPairs(a): # Initialize row sum and column # sum to zero sumr = [0 for i in range(N)] sumc = [0 for i in range(N)] # Calculate row sum and column sum for i in range(N): for j in range(N): sumr[i] += a[i][j] sumc[j] += a[i][j] count = 0 # Count the number of pairs that are valid for i in range(N): for j in range(N): if (sumc[i] > sumr[j]): count += 1 return count# Driver Codeif __name__ == '__main__': a = [[1, 2, 3],[4, 5, 6], [7, 8, 9]] print(countPairs(a)) # This code is contributed by# Surendra_Gangwar |
C#
// C# program to count the number of pairs // (i,j) such that sum of elements in j-th column // is greater than sum of elements in i-th row using System;class GFG { static int N = 3; // Function to count the number // of pairs (i,j) such that sum// of elements in j-th column is // greater than sum of elements in i-th row static int countPairs(int [,]a) { // Initialize row sum and column // sum to zero int []sumr = new int[N] ; int []sumc = new int [N] ; // Calculate row sum and column sum for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) { sumr[i] += a[i, j]; sumc[j] += a[i, j]; } int count = 0; // Count the number of pairs that are valid for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) if (sumc[i] > sumr[j]) count++; return count; } // Driver Code public static void Main() { int [,]a = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }; Console.WriteLine(countPairs(a)); } } // This code is contributed by Ryuga |
Javascript
<script> // Javascript program to count the number of pairs // (i,j) such that sum of elements in j-th column // is greater than sum of elements in i-th row let N = 3; // Function to count the number of pairs // (i,j) such that sum of elements in j-th column // is greater than sum of elements in i-th row function countPairs(a) { // Initialize row sum and column // sum to zero let sumr = new Array(N); sumr.fill(0); let sumc = new Array(N); sumc.fill(0); // Calculate row sum and column sum for (let i = 0; i < N; i++) for (let j = 0; j < N; j++) { sumr[i] += a[i][j]; sumc[j] += a[i][j]; } let count = 0; // Count the number of pairs that are valid for (let i = 0; i < N; i++) for (let j = 0; j < N; j++) if (sumc[i] > sumr[j]) count++; return count; } let a = [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]; document.write(countPairs(a));</script> |
Output
4
Time Complexity: O(N2)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
