Check given matrix is magic square or not
Given a matrix, check whether it’s Magic Square or not. A Magic Square is a n x n matrix of the distinct elements from 1 to n2 where the sum of any row, column, or diagonal is always equal to the same number.
Examples:
Input : n = 3 2 7 6 9 5 1 4 3 8 Output : Magic matrix Explanation:In matrix sum of each row and each column and diagonals sum is same = 15. Input : n = 3 1 2 2 2 2 1 2 1 2 Output : Not a Magic Matrix Explanation:In matrix sum of each row and each column and diagonals sum is not same.
- Find the sum of prime diagonal and secondary diagonal.
- Calculate the sum of each row and column.
- If the prime diagonal and secondary diagonal sums are equal to every row’s sum and every column’s sum, then it is the magic matrix.
Implementation:
C++
// C++ program to check whether a given // matrix is magic matrix or not #include <bits/stdc++.h> # define my_sizeof(type) ((char *)(&type+1)-(char*)(&type)) using namespace std; // Returns true if mat[][] is magic // square, else returns false. bool isMagicSquare( int mat[][3]) { int n = my_sizeof(mat)/my_sizeof(mat[0]); // calculate the sum of // the prime diagonal int i=0,j=0; // sumd1 and sumd2 are the sum of the two diagonals int sumd1 = 0, sumd2=0; for (i = 0; i < n; i++) { // (i, i) is the diagonal from top-left -> bottom-right // (i, n - i - 1) is the diagonal from top-right -> bottom-left sumd1 += mat[i][i]; sumd2 += mat[i][n-1-i]; } // if the two diagonal sums are unequal then it is not a magic square if (sumd1!=sumd2) return false ; // For sums of Rows for (i = 0; i < n; i++) { int rowSum = 0, colSum = 0; for (j = 0; j < n; j++) { rowSum += mat[i][j]; colSum += mat[j][i]; } if (rowSum != colSum || colSum != sumd1) return false ; } return true ; } // driver program to // test above function int main() { int mat[3][3] = {{ 2, 7, 6 }, { 9, 5, 1 }, { 4, 3, 8 }}; if (isMagicSquare(mat)) cout << "Magic Square" ; else cout << "Not a magic Square" ; return 0; } |
C
// C program to check whether a given // matrix is magic matrix or not #include <stdio.h> #include <stdbool.h> # define my_sizeof(type) ((char *)(&type+1)-(char*)(&type)) // Returns true if mat[][] is magic // square, else returns false. bool isMagicSquare( int mat[][3]) { int n = my_sizeof(mat)/my_sizeof(mat[0]); // calculate the sum of // the prime diagonal int i = 0, j = 0; // sumd1 and sumd2 are the sum of the two diagonals int sumd1 = 0, sumd2=0; for (i = 0; i < n; i++) { // (i, i) is the diagonal from top-left -> bottom-right // (i, n - i - 1) is the diagonal from top-right -> bottom-left sumd1 += mat[i][i]; sumd2 += mat[i][n-1-i]; } // if the two diagonal sums are unequal then it is not a magic square if (sumd1!=sumd2) return false ; // For sums of Rows for (i = 0; i < n; i++) { int rowSum = 0, colSum = 0; for (j = 0; j < n; j++) { rowSum += mat[i][j]; colSum += mat[j][i]; } if (rowSum != colSum || colSum != sumd1) return false ; } return true ; } // driver program to // test above function int main() { int mat[3][3] = {{ 2, 7, 6 }, { 9, 5, 1 }, { 4, 3, 8 }}; if (isMagicSquare(mat)) printf ( "Magic Square" ); else printf ( "Not a magic Square" ); return 0; } // This code is contributed by kothavvsaakash. |
Java
// JAVA program to check whether a given // matrix is magic matrix or not import java.io.*; class GFG { static int N = 3 ; // Returns true if mat[][] is magic // square, else returns false. static boolean isMagicSquare( int mat[][]) { // sumd1 and sumd2 are the sum of the two diagonals int sumd1 = 0 ,sumd2= 0 ; for ( int i = 0 ; i < N; i++) { // (i, i) is the diagonal from top-left -> bottom-right // (i, N - i - 1) is the diagonal from top-right -> bottom-left sumd1 += mat[i][i]; sumd2 += mat[i][N- 1 -i]; } // if the two diagonal sums are unequal then it is not a magic square if (sumd1!=sumd2) return false ; // calculating sums of Rows and columns and checking if they are equal to each other, // as well as equal to diagonal sum or not for ( int i = 0 ; i < N; i++) { int rowSum = 0 , colSum = 0 ; for ( int j = 0 ; j < N; j++) { rowSum += mat[i][j]; colSum += mat[j][i]; } if (rowSum != colSum || colSum != sumd1) return false ; } return true ; } // driver program to // test above function public static void main(String[] args) { int mat[][] = {{ 2 , 7 , 6 }, { 9 , 5 , 1 }, { 4 , 3 , 8 }}; if (isMagicSquare(mat)) System.out.println( "Magic Square" ); else System.out.println( "Not a magic" + " Square" ); } } |
Python3
# Python3 program to check whether a given # matrix is magic matrix or not # Returns true if mat[][] is magic # square, else returns false. def isMagicSquare( mat) : n = len (mat) # sumd1 and sumd2 are the sum of the two diagonals sumd1 = 0 sumd2 = 0 for i in range (n): # (i, i) is the diagonal from top-left -> bottom-right # (i, n - i - 1) is the diagonal from top-right -> bottom-left sumd1 + = mat[i][i] sumd2 + = mat[i][n - i - 1 ] # if the two diagonal sums are unequal then it is not a magic square if not (sumd1 = = sumd2): return False for i in range (n): #sumr is rowsum and sumc is colsum sumr = 0 sumc = 0 for j in range (n): sumr + = mat[i][j] sumc + = mat[j][i] if not (sumr = = sumc = = sumd1): return False #if all the conditions are satisfied then it is a magic square return True # Driver Code mat = [ [ 2 , 7 , 6 ], [ 9 , 5 , 1 ], [ 4 , 3 , 8 ] ] if (isMagicSquare(mat)) : print ( "Magic Square" ) else : print ( "Not a magic Square" ) |
C#
// C# program to check whether a given // matrix is magic matrix or not using System; class GFG { static int N = 3; // Returns true if mat[][] is magic // square, else returns false. static bool isMagicSquare( int [,] mat) { // sumd1 and sumd2 are the sum of the two diagonals int sumd1 = 0, sumd2 = 0; for ( int i = 0; i < N; i++) { // (i, i) is the diagonal from top-left -> bottom-right // (i, N - i - 1) is the diagonal from top-right -> bottom-left sumd1 = sumd1 + mat[i, i]; sumd2 = sumd2 + mat[i, N-1-i]; } // if the two diagonal sums are unequal then it is not a magic square if (sumd1!=sumd2) return false ; // For sums of Rows for ( int i = 0; i < N; i++) { int rowSum = 0, colSum = 0; for ( int j = 0; j < N; j++) { rowSum += mat[i, j]; colSum += mat[j,i]; } if (rowSum != colSum || colSum != sumd1) return false ; } return true ; } // Driver Code public static void Main() { int [,] mat = new int [,] {{ 2, 7, 6 }, { 9, 5, 1 }, { 4, 3, 8 }}; if (isMagicSquare(mat)) Console.WriteLine( "Magic Square" ); else Console.WriteLine( "Not a magic" + " Square" ); } } |
PHP
<?php // PHP program to check whether a given // matrix is magic matrix or not // Returns true if mat[][] is magic // square, else returns false. function isMagicSquare( $mat ) { // sumd1 and sumd2 are the sum of the two diagonals $sumd1 = 0; $sumd2 = 0; $N = count ( $mat ); for ( $i = 0; $i < $N ; $i ++) { // (i, i) is the diagonal from top-left -> bottom-right // (i, N - i - 1) is the diagonal from top-right -> bottom-left $sumd1 = $sumd1 + $mat [ $i ][ $i ]; $sumd2 = $sumd2 + $mat [ $i ][ $N - $i -1]; } // if the two diagonal sums are unequal then it is not a magic square if ( $sumd1 != $sumd2 ) return false; for ( $i = 0; $i < $N ; $i ++) { $rowSum = 0; $colSum = 0; for ( $j = 0; $j < $N ; $j ++) { $rowSum += $mat [ $i ][ $j ]; $colSum += $mat [ $j ][ $i ]; } if ( $rowSum != $colSum || $colSum != $sumd1 ) return false; } return true; } // Driver Code { $mat = array ( array (2, 7, 6), array (9, 5, 1), array (4, 3, 8)); if (isMagicSquare( $mat )) echo "Magic Square" ; else echo "Not a magic Square" ; return 0; } ?> |
Javascript
<script> // Javascript program to check whether a given // matrix is magic matrix or not // Returns true if mat[][] is magic // square, else returns false. function isMagicSquare(mat) { var N = mat.length // sumd1 and sumd2 are the sum of the two diagonals var sumd1 = 0,sumd2=0; for ( var i = 0; i < N; i++) { // (i, i) is the diagonal from top-left -> bottom-right // (i, N - i - 1) is the diagonal from top-right -> bottom-left sumd1 = sumd1 + mat[i][i]; sumd2 = sumd2 + mat[i][N-1-i]; } // if the two diagonal sums are unequal then it is not a magic square if (sumd1!=sumd2) return false ; for ( var i = 0; i < N; i++) { var colSum = 0; var rowSum = 0; for ( var j = 0; j < N; j++) { rowSum += mat[i][j]; colSum += mat[j][i]; } if (rowSum != colSum || colSum != sumd1) return false ; } return true ; } // driver program to // test above function var mat = [[ 2, 7, 6 ], [ 9, 5, 1 ], [ 4, 3, 8 ]]; if (isMagicSquare(mat)) document.write( "Magic Square" ); else document.write( "Not a magic Square" ); </script> |
Output
Magic Square
Time Complexity: O(n2)
Auxiliary Space: O(1), since no extra space has been taken.
Contact Us