For a given 2D square matrix of size N*N, the task is to find the sum of elements in the Principal and Secondary diagonals. For example, analyze the following 4 × 4 input matrix.
a00 a01 a02 a03
a10 a11 a12 a13
a20 a21 a22 a23
a30 a31 a32 a33
Example:
Input 1 : 6 7 3 4
8 9 2 1
1 2 9 6
6 5 7 2
Output 1 : Principal Diagonal: 26
Secondary Diagonal: 14
Input 2 : 2 2 2
1 1 1
3 3 3
Output 2 : Principal Diagonal: 6
Secondary Diagonal: 6
Intuition:
1. The principal diagonal is constituted by the elements a00, a11, a22, a33, and the row-column condition for the principal diagonal is: row = column
2. However, the secondary diagonal is constituted by the elements a03, a12, a21, a30, and the row-column condition for the Secondary diagonal is: row + column = N – 1
Naive approach: Use two nested loop to iterate over 2D matrix and check for the above condition for principal diagonal and secondary diagonal.
Below is the implementation of the above approach.
Java
// Java Program to Find the Sum of Diagonals of a Matrix// Importing input output classesimport java.io.*;// Main Classpublic class GFG { // To calculate Sum of Diagonals static void Sum_of_Diagonals1(int[][] matrix, int N) { // Declaring and initializing two variables to zero // initially for primary and secondary diagonal // count int Pd = 0, Sd = 0; // Two Nested for loops for iteration over a matrix // Outer loop for rows for (int k = 0; k < N; k++) { // Inner loop for columns for (int l = 0; l < N; l++) { // Condition for the principal // diagonal if (k == l) Pd += matrix[k][l]; // Condition for the secondary diagonal if ((k + l) == (N - 1)) Sd += matrix[k][l]; } } // Print and display the sum of primary diagonal System.out.println("Sum of Principal Diagonal:" + Pd); // Print and display the sum of secondary diagonal System.out.println("Sum of Secondary Diagonal:" + Sd); } // Main driver method static public void main(String[] args) { // Input integer array // Custom entries in an array int[][] b = { { 8, 2, 13, 4 }, { 9, 16, 17, 8 }, { 1, 22, 3, 14 }, { 15, 6, 17, 8 } }; // Passing the array as an argument to the // function defined above Sum_of_Diagonals1(b, 4); }} |
Sum of Principal Diagonal:35 Sum of Secondary Diagonal:58
Time complexity: O(N2)
Auxiliary space: O(1)
Efficient approach: The idea to find the sum of values of principal diagonal is to iterate to N and use the value of matrix[row][row] for the summation of principal diagonal and to find the sum of values of secondary diagonal is to use the value of matrix[row][N – (row + 1)] for summation.
Below is the implementation of the above approach.
Java
// Java Program to Find the Sum of Diagonals of a Matrix// Importing input output classesimport java.io.*;// Main Classpublic class GFG { // To calculate Sum of Diagonals static void Sum_of_Diagonals(int[][] matrix, int N) { // Declaring and initializing two variables to zero // initially for primary and secondary diagonal // count int Pd = 0, Sd = 0; for(int i=0; i<N; i++) { // Since for primary diagonal sum the value of // row and column are equal Pd += matrix[i][i]; // For secondary diagonal sum values of i'th index // and j'th index sum is equal to n-1 at each // stage of matrix Sd += matrix[i][N-(i+1)]; } // Print and display the sum of primary diagonal System.out.println("Sum of Principal Diagonal:" + Pd); // Print and display the sum of secondary diagonal System.out.println("Sum of Secondary Diagonal:" + Sd); } // Main driver method static public void main(String[] args) { // Input integer array // Custom entries in an array int[][] b = { { 8, 2, 13, 4 }, { 9, 16, 17, 8 }, { 1, 22, 3, 14 }, { 15, 6, 17, 8 } }; // Passing the array as an argument to the // function defined above Sum_of_Diagonals(b, 4); }} |
Sum of Principal Diagonal:35 Sum of Secondary Diagonal:58
Time complexity: O(N)
Auxiliary space: O(1)
