You are given an N times N matrix consisting of the numbers 1 through N^2 each o
ID: 3794003 • Letter: Y
Question
You are given an N times N matrix consisting of the numbers 1 through N^2 each occurring exactly once. Write a function to determine if A represents a magic square. The function returns a boolean. bool Is Magic Square (int A [] [], int N) {Assuming N to represent the problem size, what is the big Oh complexity of your algorithm? Justify y answer. You are to enumerate all the possible magic squares that can be determined from N. What exhaustive search problem does this resemble? Justify your answer.Explanation / Answer
bool IsMagicSquare( int A[][], int N)
{
int row_sum=0, col_ sum=0, c;
c=N((N^2)+1)/2;
for (int i = 1; i < N; i++)
{
row_sum =0;
for (int j =0; j < N; j++)
{
row_sum + = A[i][j];
for (int j =0; j < N; j++)
col_sum + = A[0][j];
if(row_sum! = c || col _sum != c)
return false;
else
return true;
}
//diagonals
row_sum=0;
for (int i=0; i<N; i++)
{
row_sum + = A[i][i];
}
If(row_sum!=c)
return false;
else
return true;
row_sum=0;
for (int i=0; i<N; i++)
{
row_sum + = A[i][2-i];
}
If(row_sum!=c)
return false;
else
return true;
}
********************************
In NxN matrix we have N^2 entries. To check if this matrix is a magic square we need to check all the entries atleast once ie N rows, N columns and two columns. This gives O((2N+2)N) = O(N2) times
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.