Matrix: Given a matrix, you need to find the sum of diagonals of a matrix.

Problem Statement:

You are given a 2D square matrix, you need to find the sum of the diagonals.

Example:

Input:

1 2 3 4
5 6 7 8
9 1 2 3
4 5 6 7

Output:

Principal diagonal sum: 1 + 6 + 2 + 7 = 16

Secondary diagonal sum: 4 + 7+ 1 + 4 = 16

Solution 1: Simple approach

Take 2 loops, one for column and one for rows.

Then in the inner loop we check for below condition:

For Principal Diagonal below is the condition:

row == column

For secondary Diagonal below is the condition:

row = number_of_rows – column – 1

Time Complexity: O(N*N)
Space Complexity: O(1)

Solution 2: Efficient approach

In this approach, we will use single loop to calculate the sum of both principal and secondary diagonals.

Code Solution

#include <iostream>
#include <vector>
using namespace std;

const int col = 10;

void solution_1(int mat[][col], int n)
{
    int pri_diagonal = 0;
    int sec_diagonal = 0;

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

            if (i == j)
                pri_diagonal += mat[i][j];

            if ((i + j) == (n - 1))
                sec_diagonal += mat[i][j];
        }
    }

    cout << "Principal Diagonal:" << pri_diagonal << endl;
    cout << "Secondary Diagonal:" << sec_diagonal << endl<<endl;
}

void solution_2 (int mat[][col], int n)
{
    int pri_diagonal = 0;
    int sec_diagonal = 0;

    for (int i = 0; i < n; i++) {
        pri_diagonal += mat[i][i];
        sec_diagonal += mat[i][n - i - 1];        
    }

    cout << "Principal Diagonal:" << pri_diagonal << endl;
    cout << "Secondary Diagonal:" << sec_diagonal << endl;
}

int main()
{
    int mat[][col] = { { 1, 2, 3, 4 }, 
                     { 5, 6, 7, 8 }, 
                     { 9, 1, 2, 3 }, 
                     { 4, 5, 6, 7 }};

    solution_1 (mat, 4);
    solution_2 (mat, 4);

    return 0;
}

Output

Principal Diagonal:16
Secondary Diagonal:16

Principal Diagonal:16
Secondary Diagonal:16