Sum of matrix in which each element is absolute difference of its row and column numbers
Given a positive integer n. Consider a matrix of n rows and n columns, in which each element contain absolute difference of its row number and numbers. The task is to calculate sum of each element of the matrix.
Examples :
Input : n = 2 Output : 2 Matrix formed with n = 2 with given constraint: 0 1 1 0 Sum of matrix = 2. Input : n = 3 Output : 8 Matrix formed with n = 3 with given constraint: 0 1 2 1 0 1 2 1 0 Sum of matrix = 8.
Method 1 (Brute Force): Simply construct a matrix of n rows and n columns and initialize each cell with absolute difference of its corresponding row number and column number. Now, find the sum of each cell.
Below is the implementation of above idea :
C++
// C++ program to find sum of matrix in which each // element is absolute difference of its corresponding // row and column number row. #include<bits/stdc++.h> using namespace std; // Return the sum of matrix in which each element // is absolute difference of its corresponding row // and column number row int findSum( int n) { // Generate matrix int arr[n][n]; for ( int i = 0; i < n; i++) for ( int j = 0; j < n; j++) arr[i][j] = abs (i - j); // Compute sum int sum = 0; for ( int i = 0; i < n; i++) for ( int j = 0; j < n; j++) sum += arr[i][j]; return sum; } // Driven Program int main() { int n = 3; cout << findSum(n) << endl; return 0; } |
Java
// Java program to find sum of matrix // in which each element is absolute // difference of its corresponding // row and column number row. import java.io.*; public class GFG { // Return the sum of matrix in which // each element is absolute difference // of its corresponding row and column // number row static int findSum( int n) { // Generate matrix int [][]arr = new int [n][n]; for ( int i = 0 ; i < n; i++) for ( int j = 0 ; j < n; j++) arr[i][j] = Math.abs(i - j); // Compute sum int sum = 0 ; for ( int i = 0 ; i < n; i++) for ( int j = 0 ; j < n; j++) sum += arr[i][j]; return sum; } // Driver Code static public void main (String[] args) { int n = 3 ; System.out.println(findSum(n)); } } // This code is contributed by vt_m. |
Python3
# Python3 program to find sum of matrix # in which each element is absolute # difference of its corresponding # row and column number row. # Return the sum of matrix in which each # element is absolute difference of its # corresponding row and column number row def findSum(n): # Generate matrix arr = [[ 0 for x in range (n)] for y in range (n)] for i in range (n): for j in range (n): arr[i][j] = abs (i - j) # Compute sum sum = 0 for i in range (n): for j in range (n): sum + = arr[i][j] return sum # Driver Code if __name__ = = "__main__" : n = 3 print (findSum(n)) # This code is contributed by ita_c |
C#
// C# program to find sum of matrix // in which each element is absolute // difference of its corresponding // row and column number row. using System; public class GFG { // Return the sum of matrix in which // each element is absolute difference // of its corresponding row and column // number row static int findSum( int n) { // Generate matrix int [,]arr = new int [n, n]; for ( int i = 0; i < n; i++) for ( int j = 0; j < n; j++) arr[i,j ] = Math.Abs(i - j); // Compute sum int sum = 0; for ( int i = 0; i < n; i++) for ( int j = 0; j < n; j++) sum += arr[i, j]; return sum; } // Driver Code static public void Main(String[] args) { int n = 3; Console.WriteLine(findSum(n)); } } // This code is contributed by vt_m. |
PHP
<?php // PHP program to find sum of // matrix in which each element // is absolute difference of // its corresponding row and // column number row. // Return the sum of matrix // in which each element // is absolute difference // of its corresponding row // and column number row function findSum( $n ) { // Generate matrix $arr = array ( array ()); for ( $i = 0; $i < $n ; $i ++) for ( $j = 0; $j < $n ; $j ++) $arr [ $i ][ $j ] = abs ( $i - $j ); // Compute sum $sum = 0; for ( $i = 0; $i < $n ; $i ++) for ( $j = 0; $j < $n ; $j ++) $sum += $arr [ $i ][ $j ]; return $sum ; } // Driver Code $n = 3; echo findSum( $n ); // This code is contributed by anuj_67. ?> |
Javascript
<script> // Javascript program to find sum of matrix // in which each element is absolute // difference of its corresponding // row and column number row. // Return the sum of matrix in which // each element is absolute difference // of its corresponding row and column // number row function findSum(n) { // Generate matrix let arr= new Array(n); for (let i = 0; i < n; i++) { arr[i] = new Array(n); for (let j = 0; j < n; j++) { arr[i][j] = 0; } } for (let i = 0; i < n; i++) for (let j = 0; j < n; j++) arr[i][j] = Math.abs(i - j); // Compute sum let sum = 0; for (let i = 0; i < n; i++) for (let j = 0; j < n; j++) sum += arr[i][j]; return sum; } // Driver Code let n = 3; document.write(findSum(n)); // This code is contributed by avanitrachhadiya2155 </script> |
8
Time Complexity: O(N2), as we are traversing the matrix using nested loops.
Auxiliary Space: O(N2), as we are using extra space for generating and storing the Matrix.
Method 2 (O(n)):
Consider n = 3, matrix formed will be:
0 1 2
1 0 1
2 1 0
Observe, the main diagonal is always 0 since all i are equal to j. The diagonal just above and just below will always be 1 because at each cell either i is 1 greater than j or j is 1 greater than i and so on.
Following the pattern we can see that the total sum of all the elements in the matrix will be, for each i from 0 to n, add i*(n-i)*2.
Below is the implementation of above idea :
C++
// C++ program to find sum of matrix in which // each element is absolute difference of its // corresponding row and column number row. #include<bits/stdc++.h> using namespace std; // Return the sum of matrix in which each // element is absolute difference of its // corresponding row and column number row int findSum( int n) { int sum = 0; for ( int i = 0; i < n; i++) sum += i*(n-i); return 2*sum; } // Driven Program int main() { int n = 3; cout << findSum(n) << endl; return 0; } |
Java
// Java program to find sum of matrix in which // each element is absolute difference of its // corresponding row and column number row. import java.io.*; class GFG { // Return the sum of matrix in which each // element is absolute difference of its // corresponding row and column number row static int findSum( int n) { int sum = 0 ; for ( int i = 0 ; i < n; i++) sum += i * (n - i); return 2 * sum; } // Driver Code static public void main(String[] args) { int n = 3 ; System.out.println(findSum(n)); } } // This code is contributed by vt_m. |
C#
// C# program to find sum of matrix in which // each element is absolute difference of its // corresponding row and column number row. using System; class GFG { // Return the sum of matrix in which each // element is absolute difference of its // corresponding row and column number row static int findSum( int n) { int sum = 0; for ( int i = 0; i < n; i++) sum += i * (n - i); return 2 * sum; } // Driver Code static public void Main(String[] args) { int n = 3; Console.WriteLine(findSum(n)); } } // This code is contributed by vt_m. |
Python3
# Python 3 program to find sum # of matrix in which each element # is absolute difference of its # corresponding row and column # number row. # Return the sum of matrix in # which each element is absolute # difference of its corresponding # row and column number row def findSum(n): sum = 0 for i in range (n): sum + = i * (n - i) return 2 * sum # Driver code n = 3 print (findSum(n)) # This code is contributed by Shrikant13 |
PHP
<?php // PHP program to find sum of matrix in which // each element is absolute difference of its // corresponding row and column number row. // Return the sum of matrix in which each // element is absolute difference of its // corresponding row and column number row function findSum( $n ) { $sum = 0; for ( $i = 0; $i < $n ; $i ++) $sum += $i * ( $n - $i ); return 2 * $sum ; } // Driver Code $n = 3; echo findSum( $n ); // This code is contributed by anuj_67. ?> |
Javascript
<script> // Java script program to find sum of matrix in which // each element is absolute difference of its // corresponding row and column number row. // Return the sum of matrix in which each // element is absolute difference of its // corresponding row and column number row function findSum( n) { let sum = 0; for (let i = 0; i < n; i++) sum += i * (n - i); return 2 * sum; } // Driver Code let n = 3; document.write(findSum(n)); // This code is contributed by mohan pavan </script> |
8
Time Complexity: O(N), as we are only using single loop to traverse.
Auxiliary Space: O(1), as we are not using any extra space.
Method 3 (Trick):
Consider n = 3, matrix formed will be:
0 1 2
1 0 1
2 1 0
So, sum = 1 + 1 + 1 + 1 + 2 + 2.
On Rearranging, 1 + 2 + 1 + 2 + 2 = 1 + 2 + 1 + 22.
So, in every case we can rearrange the sum of matrix so that the answer always will be sum of first n – 1 natural number and sum of square of first n – 1 natural number.
Sum of first n natural number = ((n)*(n + 1))/2. Sum of first n natural number = ((n)*(n + 1)*(2*n + 1)/6.
Below is the implementation of above idea :
C++
// C++ program to find sum of matrix in which // each element is absolute difference of its // corresponding row and column number row. #include<bits/stdc++.h> using namespace std; // Return the sum of matrix in which each element // is absolute difference of its corresponding // row and column number row int findSum( int n) { n--; int sum = 0; sum += (n*(n+1))/2; sum += (n*(n+1)*(2*n + 1))/6; return sum; } // Driven Program int main() { int n = 3; cout << findSum(n) << endl; return 0; } |
Java
// Java program to find sum of matrix in which // each element is absolute difference of its // corresponding row and column number row. import java.io.*; public class GFG { // Return the sum of matrix in which each element // is absolute difference of its corresponding // row and column number row static int findSum( int n) { n--; int sum = 0 ; sum += (n * (n + 1 )) / 2 ; sum += (n * (n + 1 ) * ( 2 * n + 1 )) / 6 ; return sum; } // Driver Code static public void main (String[] args) { int n = 3 ; System.out.println(findSum(n)); } } // This code is contributed by vt_m. |
Python3
# Python 3 program to find sum of matrix # in which each element is absolute # difference of its corresponding row # and column number row. # Return the sum of matrix in which # each element is absolute difference # of its corresponding row and column # number row def findSum(n): n - = 1 sum = 0 sum + = (n * (n + 1 )) / 2 sum + = (n * (n + 1 ) * ( 2 * n + 1 )) / 6 return int ( sum ) # Driver Code n = 3 print (findSum(n)) # This code contributed by Rajput-Ji |
C#
// C# program to find sum of matrix in which // each element is absolute difference of its // corresponding row and column number row. using System; public class GFG { // Return the sum of matrix in which each element // is absolute difference of its corresponding // row and column number row static int findSum( int n) { n--; int sum = 0; sum += (n * (n + 1)) / 2; sum += (n * (n + 1) * (2 * n + 1)) / 6; return sum; } // Driver Code static public void Main(String[] args) { int n = 3; Console.WriteLine(findSum(n)); } } // This code is contributed by vt_m. |
PHP
<?php // PHP program to find sum of // matrix in which each element // is absolute difference of its // corresponding row and column // number row. // Return the sum of matrix in // which each element is absolute // difference of its corresponding // row and column number row function findSum( $n ) { $n --; $sum = 0; $sum += ( $n * ( $n + 1)) / 2; $sum += ( $n * ( $n + 1) * (2 * $n + 1)) / 6; return $sum ; } // Driver Code $n = 3; echo findSum( $n ) ; // This code is contributed // by nitin mittal. ?> |
Javascript
<script> // Java script program to find sum of matrix in which // each element is absolute difference of its // corresponding row and column number row. // Return the sum of matrix in which each element // is absolute difference of its corresponding // row and column number row function findSum( n) { n--; let sum = 0; sum += (n * (n + 1)) / 2; sum += (n * (n + 1) * (2 * n + 1)) / 6; return sum; } // Driver Code let n = 3; document.write(findSum(n)); // This code is contributed by mohan pavan </script> |
8
Time Complexity: O(1), as we are not using any loops.
Auxiliary Space: O(1), as we are not using any extra space.