calculate the sum of diagonals in a matrix

Question

I need to calculate the sum of two diagonals in a matrix in C++, I already have a solution for that but I must be dumb because I cant understand what it is doing, so I would like to know if there is another version which I can understand. here is the code which does the job:

cout<<"Jepi rangun e  matrices"<<endl;  // pra bejme manipulim me matrice katrore ku rreshtat=kolonat
cin>>n;
cout<<"Tani jepi elementet e matrices"<<endl; // lexohet matrica

for(i=1;i<=n;i++)
{
     for(j=1;j<=n;j++)
        cin>>a[i][j];
}

d=0;
s=0; // ketu e keni kushtin si dhe mbledhjen per te dy diagonalet me dy variabla te ndryshme

for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    {
        if(i==j)
            d=d+a[i][j];
        if(j==n-i+1 || i==n-j+1) 
            s=s+a[i][j];
    }

The part that is difficult to understand is

if(j==n-i+1 || i==n-j+1) 
    s=s+a[i][j];

Here is the entire code that I changed but it doesnt work for the secondary diagonal:

#include <iostream>
using namespace std;

int main()
{
    int d=0,s=0; // ketu e keni kushtin si dhe mbledhjen per te dy diagonalet me dy variabla te ndryshme
    int i,j,n;
    int a[5][5];

    cout<<"Jepi rangun e  matrices"<<endl;  // pra bejme manipulim me matrice katrore ku rreshtat=kolonat
    cin>>n;
    cout<<"Tani jepi elementet e matrices"<<endl; // lexohet matrica

    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
            cin>>a[i][j];
    }

    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            if(i==j) 
                d+=a[i][j]; //principal diagonal 
            if(i+j==n-1)
                s+=a[i][j];//secondary diagonal

        }
    }

    cout << d << endl;
    cout << s << endl;
    cin.get();
    cin.get();
    return 0;
}

Solution 1

It would be nice to have comments in English, but, the your code does (second loop):

browse all rows
  browse all cells
    if i == j (is in main diagonal):
        increase one sum
    if i == n - i + 1 (the other diagonal)
        increase the second sum

The much nicer and much more effective code (using n, instead of n^2) would be:

for( int i = 0; i < n; i++){
   d += a[i][i];  // main diagonal
   s += a[i][n-i-1]; // second diagonal (you'll maybe need to update index)
}

This goes straight trough the diagonals (both at the one loop!) and doesn't go trough other items.

EDIT:

Main diagonal has coordinates {(1,1), (2,2), ..., (i,i)} (therefor i == j).

Secondary diagonal has coordinates (in matrix 3x3): {(1,3), (2,2),(3,1)} which in general is: {(1,n-1+1), (2, n-2+1), ... (i, n-i+1), .... (n,1)}. But in C, arrays are indexed from 0, not 1 so you won't need that +1 (probably).

All those items in secondary diagonal than has to fit condition: i == n - j + 1 (again due to C's indexing from 0 +1 changes to -1 (i=0,, n=3, j=2, j = n - i - 1)).

You can achieve all this in one loop (code above).

Solution 2

int diag1=0;
int diag2=0;

for (i=0;i<n;i++)
 for (j=0;j<n;j++){

  if(i==j)  diag1+=a[i][j]; //principal diagonal 
  if(i+j==n-1) diag2+=a[i][j];//secondary diagonal

}

To understand this algorithm better you should paint a matrix on you notebook and number it's elements with their position in matrix,then apply the algorithm step by step.I'm 100% sure that you will understand

Solution 3

How about I try to explain this version? :D

There are 3 important parts of the code:

• inputing the matrix
• calculating major diagonal ( \ direction)
• calculating minor diagonal ( / direction)

And here they are, explained:

// input elements
for(i=1;i<=n;i++) // from left to right
{
    for(j=1;j<=n;j++) // from up to down
        cin>>a[i][j]; // input element at (i,j) position
}

Here, d and s contain the inter-values of major and minor diagonal respectively. At the end of 2 loops, they will contain the results

for (i=1;i<=n;i++)
     for (j=1;j<=n;j++)
     {
        if(i==j)          // major diagonal - if coordinates are the same
           d=d+a[i][j];   // e.g. (1,1), (2,2)
        if(j==n-i+1 || i==n-j+1)  // coordinates of the minor diagonal - check
           s=s+a[i][j];           // e.g. n=3 (3,1) (2,2) ...
      }

Hope this helps.

Note that this code starts matrix coordinates at 1 instead of 0, so you will actually need to allocate (n+1)x(n+1) space for the matrix:

double a[n+1][n+1];

before using it.

Also, the code you gave is not most effective. It has O(n^2) complexity, while the task can be done in O(n) like so:

// matrix coordinates now start from 0
for (int i=0; i < n; ++i){
    d += a[i][i]; // major
    s += a[i][n-1-i]; // minor
}

Comments

[Igor Ivanovski]

Yeah I painted the matrix but yet I got lost.. but now I understand it after I saw your code this was helpful: if(i+j=n-1)

[Ionel Lupu]

Try to do what the computer does.Use n=3 and this values a(1,1) a(1,2) a(1,3), a(2,1) a(2,2) a(2,3), a(3,1) a(3,2) a(3,3) (change the a in a number) Then go in for loop and note your i and j and then check the if's

[Igor Ivanovski]

I tried this in C++ and it didnt work for the secondary diagonal

[Ionel Lupu]

well my algorithm use this for the for loop(i=0;i<n;i++).But for you for loop write this for the secondary diagonal if(i+j==n+1)

[Vyktor]

@cyborg n=5; i=0; that would mean that second index j=6; which is out of boundaries (I assume j=4 is correct in this case).

[Abdul Rehman]

I think this is the simplest solution for this matrix. . . .!!