Given a matrix M[][] of dimensions N * N, consisting only of integers from the range 1 to N, the task is to compute the sum of the matrix elements present in the main diagonal, the number of rows and columns containing repeated values.
Examples:
Input: N = 4, M[][] = {{1, 2, 3, 4}, {2, 1, 4, 3}, {3, 4, 1, 2}, {4, 3, 2, 1}}
Output: 4 0 0
Explanation:
Sum of diagonal = M[0][0] + M[1][1] + M[2][2] + M[3][3] = 4.
No row or column consists of repeated elements.
Therefore, the required sum is 4Input: N = 3, M[][] = {{2, 1, 3}, {1, 3, 2}, {1, 2, 3}}
Output: 8 0 2
Explanation:
Sum of diagonal = M[0][0]+M[1][1]+M[2][2] = 8.
No row consists of repeated elements.
1st and 3rd columns consists of repeated elements.
Approach: The approach is to simply traverse all elements of the matrix and find the sum of diagonals and the number of rows and columns having repeated values. Follow the steps below to solve the given problem:
- Initialize variables trace, rowRepeat, and columnRepeat to store the sum of the main diagonal, the number of rows, and columns containing repeated matrix elements respectively.
- Traverse through each element present in the matrix M[i][j] and increment the sum trace if i is equal to j.
- To find rows containing repeated values, iterate over one row at a time, compare values, and check if there exists a repeated value or not. On getting the first pair of repeat element, increment rowRepeat by 1 and break out of the loop.
- Repeat the above steps for every row of the matrix.
- The same procedure is repeated for all columns, where columnRepeat is incremented by 1 if the values match.
- After completing all the iterations, print the value of trace, rowRepeat, and columnRepeat as the result.
Below is the implementation of the above approach:
C++14
// C++14 program for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate trace of// a matrix and number of rows and// columns with repeated elementsvoid vestigium(int N, int M[4][4]){ // Stores the trace, number of // rows and columns consisting // of repeated matrix elements int trace = 0, row_repeat = 0; int column_repeat = 0; // Iterate over the matrix for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { // If current element is // present in the main diagonal if (i == j) { // Update trace trace += M[i][j]; } } int flag1 = 0; // Iterate over each row // and increment row_repeat // if repeated values exists for(int j = 0; j < N; j++) { for(int k = 0; k < N; k++) { // For each valid range if (j != k && M[i][j] == M[i][k]) { row_repeat++; flag1 = 1; break; } } if (flag1 == 1) { break; } } int flag2 = 0; // Iterate over each column and // increment column_repeat if // repeated values are encountered for(int j = 0; j < N; j++) { for(int k = 0; k < N; k++) { // For each valid range if (j != k && M[j][i] == M[k][i]) { column_repeat++; flag2 = 1; break; } } if (flag2 == 1) { break; } } } // Answer cout << trace << " " << row_repeat << " " << column_repeat ;}// Driver Codeint main(){ int M[4][4] = { { 1, 2, 3, 4 }, { 2, 1, 4, 3 }, { 3, 4, 1, 2 }, { 4, 3, 2, 1 } }; int N = sizeof(M) / sizeof(M[0]); vestigium(N, M);}// This code is contributed by sanjoy_62 |
Java
// Java program for the above approachpublic class GFG { // Function to calculate trace of // a matrix and number of rows and // columns with repeated elements public static String vestigium( int N, int M[][]) { // Stores the trace, number of // rows and columns consisting // of repeated matrix elements int trace = 0, row_repeat = 0; int column_repeat = 0; // Iterate over the matrix for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { // If current element is // present in the main diagonal if (i == j) { // Update trace trace += M[i][j]; } } int flag1 = 0; // Iterate over each row // and increment row_repeat // if repeated values exists for (int j = 0; j < N; j++) { for (int k = 0; k < N; k++) { // For each valid range if (j != k && M[i][j] == M[i][k]) { row_repeat++; flag1 = 1; break; } } if (flag1 == 1) { break; } } int flag2 = 0; // Iterate over each column and // increment column_repeat if // repeated values are encountered for (int j = 0; j < N; j++) { for (int k = 0; k < N; k++) { // For each valid range if (j != k && M[j][i] == M[k][i]) { column_repeat++; flag2 = 1; break; } } if (flag2 == 1) { break; } } } // Answer String output = trace + " " + row_repeat + " " + column_repeat + "\n"; // Return answer return output; } // Driver Code public static void main(String[] args) { int M[][] = { { 1, 2, 3, 4 }, { 2, 1, 4, 3 }, { 3, 4, 1, 2 }, { 4, 3, 2, 1 } }; int N = M.length; String output = vestigium(N, M); // Print the output System.out.print(output); }} |
Python3
# Python3 program for the above approach# Function to calculate trace of# a matrix and number of rows and# columns with repeated elementsdef vestigium(N, M) : # Stores the trace, number of # rows and columns consisting # of repeated matrix elements trace = 0 row_repeat = 0 column_repeat = 0 # Iterate over the matrix for i in range(N) : for j in range(N) : # If current element is # present in the main diagonal if (i == j): # Update trace trace += M[i][j] flag1 = 0 # Iterate over each row # and increment row_repeat # if repeated values exists for j in range(N) : for k in range(N) : # For each valid range if (j != k and M[i][j] == M[i][k]) : row_repeat += 1 flag1 = 1 break if (flag1 == 1) : break flag2 = 0 # Iterate over each column and # increment column_repeat if # repeated values are encountered for j in range(N) : for k in range(N) : # For each valid range if (j != k and M[j][i] == M[k][i]) : column_repeat += 1 flag2 = 1 break if (flag2 == 1) : break # Answer print(trace, row_repeat, column_repeat)# Driver CodeM = [[ 1, 2, 3, 4 ], [ 2, 1, 4, 3 ], [ 3, 4, 1, 2 ], [ 4, 3, 2, 1 ]] N = len(M) vestigium(N, M)# This code is contributed by avijitmonald1998. |
C#
// C# program for the above approachusing System;class GFG{// Function to calculate trace of// a matrix and number of rows and// columns with repeated elementspublic static String vestigium(int N, int[,] M){ // Stores the trace, number of // rows and columns consisting // of repeated matrix elements int trace = 0, row_repeat = 0; int column_repeat = 0; // Iterate over the matrix for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { // If current element is // present in the main diagonal if (i == j) { // Update trace trace += M[i, j]; } } int flag1 = 0; // Iterate over each row // and increment row_repeat // if repeated values exists for(int j = 0; j < N; j++) { for(int k = 0; k < N; k++) { // For each valid range if (j != k && M[i, j] == M[i, k]) { row_repeat++; flag1 = 1; break; } } if (flag1 == 1) { break; } } int flag2 = 0; // Iterate over each column and // increment column_repeat if // repeated values are encountered for(int j = 0; j < N; j++) { for(int k = 0; k < N; k++) { // For each valid range if (j != k && M[j, i] == M[k, i]) { column_repeat++; flag2 = 1; break; } } if (flag2 == 1) { break; } } } // Answer string output = trace + " " + row_repeat + " " + column_repeat + "\n"; // Return answer return output;}// Driver Codepublic static void Main(string[] args){ int[, ] M = { { 1, 2, 3, 4 }, { 2, 1, 4, 3 }, { 3, 4, 1, 2 }, { 4, 3, 2, 1 } }; int N = M.GetLength(0); string output = vestigium(N, M); // Print the output Console.Write(output);}}// This code is contributed by ukasp |
Javascript
<script>// javascript program for the above approach// Function to calculate trace of// a matrix and number of rows and// columns with repeated elementsfunction vestigium( N , M){ // Stores the trace, number of // rows and columns consisting // of repeated matrix elements var trace = 0, row_repeat = 0; var column_repeat = 0; // Iterate over the matrix for (i = 0; i < N; i++) { for (j = 0; j < N; j++) { // If current element is // present in the main diagonal if (i == j) { // Update trace trace += M[i][j]; } } var flag1 = 0; // Iterate over each row // and increment row_repeat // if repeated values exists for (j = 0; j < N; j++) { for (k = 0; k < N; k++) { // For each valid range if (j != k && M[i][j] == M[i][k]) { row_repeat++; flag1 = 1; break; } } if (flag1 == 1) { break; } } var flag2 = 0; // Iterate over each column and // increment column_repeat if // repeated values are encountered for (j = 0; j < N; j++) { for (k = 0; k < N; k++) { // For each valid range if (j != k && M[j][i] == M[k][i]) { column_repeat++; flag2 = 1; break; } } if (flag2 == 1) { break; } } } // Answer var output = trace + " " + row_repeat + " " + column_repeat + "\n"; // Return answer return output;}// Driver Code var M = [ [ 1, 2, 3, 4 ], [ 2, 1, 4, 3 ], [ 3, 4, 1, 2 ], [ 4, 3, 2, 1 ] ]; var N = M.length; var output = vestigium(N, M); // Print the output document.write(output);// This code contributed by shikhasingrajput </script> |
Output:
4 0 0
Time Complexity: O(N3)
Auxiliary Space: O(N2)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
