Find diagonal sum of given Matrix when mat[i][j] is product of arr[i] and arr[j]
Given an matrix mat[][] of size N*N (N > 2) such that mat[i][j] = arr[i]*arr[j] (where arr[] is a N sized array that is not provided). The elements along the primary diagonal (top-left to bottom-right) are missing (represented as 0), the task is to find the sum of these missing elements.
Examples:
Input: N = 5, mat[][] = {{0, 4, 6, 2, 4}, {4, 0, 6, 2, 4}, {6, 6, 0, 3, 6}, {2, 2, 3, 0, 2}, {4, 4, 6, 2, 0}}
Output: 22
Explanation: The array whose elements are multiplied
to get the matrix is arr[] = {2, 2, 3, 1, 2}.
The diagonal elements of the matrix will be a[0]*a[0], a[1]*a[1], a[2]*a[2]
as for diagonal elements i = j .
So the sum of diagonal elements will be 4+4+9+1+4 =22Input: N = 3, mat[][] = {{0, 1, 2}, {1, 0, 2}, {2, 2, 0}}
Output: 6
Approach: The problem can be solved based on the below mathematical idea:
The diagonal elements of the matrix are arr[0]*arr[0], arr[1]*arr[1], arr[2]*arr[2], . . .
In order to find arr[0]*arr[0], we can do the following:
(mat[0][1]*mat[0][2])/mat[1][2] = arr[0]*arr[1]*arr[0]*arr[2]/(arr[1]*arr[2]) = arr[0]*arr[0] then square root of it will give arr[0].Once we get arr[0] we can easily get all the other elements by dividing the elements of the first row with arr[0].
Follow the steps mentioned below to implement the idea:
- Calculate the value of any array element using the above idea (Here we are finding value of arr[0]).
- Divide the elements of the first row with arr[0] to get the other values.
- Now calculate the values along the diagonal and add them to get the answer.
Below is the implementation of the above approach.
C++14
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to find the sum of the diagonal elements int findres(vector<vector< int > >& m, int N) { int res = 0; int x = (m[0][2] * m[0][1]) / m[1][2]; res += x; int a0 = sqrt (x); for ( int i = 1; i < N; i++) { int temp = m[0][i] / a0; res += (temp * temp); } return res; } // Driver code int main() { vector<vector< int > > mat = { { 0, 4, 6, 2, 4 }, { 4, 0, 6, 2, 4 }, { 6, 6, 0, 3, 6 }, { 2, 2, 3, 0, 2 }, { 4, 4, 6, 2, 0 } }; int N = mat.size(); // Function call cout << findres(mat, N) << endl; return 0; } |
Java
// Java code to implement approach import java.io.*; import java.util.*; import java.lang.Math; class HelloWorld { static int findres( int m[][], int N) { int res = 0 ; int x = (m[ 0 ][ 2 ] * m[ 0 ][ 1 ]) / m[ 1 ][ 2 ]; res += x; double a = Math.sqrt(x); int a0= ( int )a; for ( int i = 1 ; i < N; i++) { int temp = (m[ 0 ][i] / a0); res += (temp * temp); } return res; } public static void main(String[] args) { int [][] mat = { { 0 , 4 , 6 , 2 , 4 }, { 4 , 0 , 6 , 2 , 4 }, { 6 , 6 , 0 , 3 , 6 }, { 2 , 2 , 3 , 0 , 2 }, { 4 , 4 , 6 , 2 , 0 } }; int N = mat.length; // Function call System.out.println(findres(mat, N)); } } // this code is contributed by ksam24000 |
Python3
# Python code for the above approach import math # Function to find the sum of the diagonal elements def findres(m, N): res = 0 x = (m[ 0 ][ 2 ] * m[ 0 ][ 1 ]) / m[ 1 ][ 2 ] res + = x a0 = math.sqrt(x) for i in range ( 1 , N): temp = m[ 0 ][i] / a0 res + = (temp * temp) return int (res) mat = [[ 0 , 4 , 6 , 2 , 4 ], [ 4 , 0 , 6 , 2 , 4 ], [ 6 , 6 , 0 , 3 , 6 ], [ 2 , 2 , 3 , 0 , 2 ], [ 4 , 4 , 6 , 2 , 0 ]] N = len (mat) # Function call print (findres(mat, N)) # This is code is contributed by lokesh |
C#
// C# code to implement the approach using System; using System.Collections.Generic; public class GFG { static int findres( int [,] m, int N) { int res = 0; int x = (m[0, 2] * m[0, 1]) / m[1, 2]; res += x; double a = Math.Sqrt(x); int a0= ( int )a; for ( int i = 1; i < N; i++) { int temp = (m[0, i] / a0); res += (temp * temp); } return res; } // Driver Code public static void Main( string [] args) { int [,] mat = { { 0, 4, 6, 2, 4 }, { 4, 0, 6, 2, 4 }, { 6, 6, 0, 3, 6 }, { 2, 2, 3, 0, 2 }, { 4, 4, 6, 2, 0 } }; int N = mat.GetLength(0); // Function call Console.WriteLine(findres(mat, N)); } } // This code is contributed by sanjoy_62. |
Javascript
<script> // JavaScript code for the above approach // Function to find the sum of the diagonal elements function findres(m, N) { let res = 0; let x = (m[0][2] * m[0][1]) / m[1][2]; res += x; let a0 = Math.sqrt(x); for (let i = 1; i < N; i++) { let temp = m[0][i] / a0; res += (temp * temp); } return res; } // Driver code let mat = [[0, 4, 6, 2, 4], [4, 0, 6, 2, 4], [6, 6, 0, 3, 6], [2, 2, 3, 0, 2], [4, 4, 6, 2, 0]]; let N = mat.length; // Function call document.write(findres(mat, N)); // This code is contributed by Potta Lokesh </script> |
22
Time Complexity: O(N) as we are only iterating the first row of size N.
Auxiliary Space: O(1)