Find sum of all elements in a matrix except the elements in row and/or column of given cell? - GeeksforGeeks

Find sum of all elements in a matrix except the elements in row and/or column of given cell? - GeeksforGeeks
Given a 2D matrix and a set of cell indexes e.g., an array of (i, j) where i indicates row and j column. For every given cell index (i, j), find sums of all matrix elements except the elements present in i'th row and/or j'th column.

Example:
mat[][]  = { {1, 1, 2}
             {3, 4, 6}
             {5, 3, 2} }
Array of Cell Indexes: {(0, 0), (1, 1), (0, 1)}
Output:  15, 10, 16

An Efficient Solution can compute all sums in O(R x C + n) time. The idea is to precompute total sum, row and column sums before processing the given array of indexes. Below are details
1. Calculate sum of matrix, call it sum.
2. Calculate sum of individual rows and columns. (row[] and col[])
3. For a cell index (i, j), the desired sum will be “sum- row[i] – col[j] + arr[i][j]”
Time Complexity: O(R x C + n)
Auxiliary Space: O(R + C)

struct Cell

{

    int r; // r is row, varies from 0 to R-1

    int c; // c is column, varies from 0 to C-1

};

 

void printSums(int mat[][C], struct Cell arr[], int n)

{

    int sum = 0;

    int row[R] = {};

    int col[C] = {};

 

    // Compute sum of all elements, sum of every row and sum every column

    for (int i=0; i<R; i++)

    {

      for (int j=0; j<C; j++)

       {

             sum += mat[i][j];

             col[i] += mat[j][i];

             row[i] += mat[i][j];

       }

    }

 

    // Compute the desired sum for all given cell indexes

    for (int i=0; i<n; i++)

    {

        int ro = arr[i].r, co = arr[i].c;

        cout << sum - row[ro] - col[co] + mat[ro][co] << endl;

    }

}

Read full article from Find sum of all elements in a matrix except the elements in row and/or column of given cell? - GeeksforGeeks