Given a 2D square matrix, find the sum of elements in Principal and Secondary diagonals. For example, consider the following 4 X 4 input matrix.
A00 A01 A02 A03 A10 A11 A12 A13 A20 A21 A22 A23 A30 A31 A32 A33
The primary diagonal is formed by the elements A00, A11, A22, A33.
- Condition for Principal Diagonal: The row-column condition is row = column.
The secondary diagonal is formed by the elements A03, A12, A21, A30. - Condition for Secondary Diagonal: The row-column condition is row = numberOfRows – column -1.
Examples :
Input: 4 1 2 3 4 4 3 2 1 7 8 9 6 6 5 4 3 Output: Principal Diagonal: 16 Secondary Diagonal: 20 Input: 3 1 1 1 1 1 1 1 1 1 Output: Principal Diagonal: 3 Secondary Diagonal: 3
Method 1 (Brute Force) :
In this method, we use two loops i.e. a loop for columns and a loop for rows and in the inner loop we check for the condition stated above:
C++
// A simple C++ program to find sum // of diagonals #include <bits/stdc++.h> using namespace std; const int MAX = 100; void printDiagonalSums(int mat[][MAX], int n) { int principal = 0, secondary = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { // Condition for principal diagonal if (i == j) principal += mat[i][j]; // Condition for secondary diagonal if ((i + j) == (n - 1)) secondary += mat[i][j]; } } cout << "Principal Diagonal:" << principal << endl; cout << "Secondary Diagonal:" << secondary << endl; } // Driver code int main() { int a[][MAX] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {1, 2, 3, 4}, {5, 6, 7, 8}}; printDiagonalSums(a, 4); return 0; } |
Output:
Principal Diagonal:18 Secondary Diagonal:18
Time Complexity: O(N*N), as we are using nested loops to traverse N*N times.
Auxiliary Space: O(1), as we are not using any extra space.
Method 2 (Efficient Approach) :
In this method we use one loop i.e. a loop for calculating sum of both the principal and secondary diagonals:
C++
// An efficient C++ program to // find sum of diagonals #include <bits/stdc++.h> using namespace std; const int MAX = 100; void printDiagonalSums(int mat[][MAX], int n) { int principal = 0, secondary = 0; for (int i = 0; i < n; i++) { principal += mat[i][i]; secondary += mat[i][n - i - 1]; } cout << "Principal Diagonal:" << principal << endl; cout << "Secondary Diagonal:" << secondary << endl; } // Driver code int main() { int a[][MAX] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {1, 2, 3, 4}, {5, 6, 7, 8}}; printDiagonalSums(a, 4); return 0; } |
Output :
Principal Diagonal:18 Secondary Diagonal:18
Time Complexity: O(N), as we are using a loop to traverse N times.
Auxiliary Space: O(1), as we are not using any extra space.
Please refer complete article on Efficiently compute sums of diagonals of a matrix for more details!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
