# Question 3

## Given an n x n square matrix, find sum of all sub-squares of size k x k

Given an n x n square matrix, find sum of all sub-squares of size k x k where k is smaller than or equal to n.

## How to solve this problem

A Simple Solution is to one by one pick starting point (leftmost-topmost corner) of all possible sub-squares. Once the starting point is picked, calculate sum of sub-square starting with the picked starting point.

Examples :

• Sample Input 1:
• n = 5, k = 3
• arr[][] = { {1, 1, 1, 1, 1},
{2, 2, 2, 2, 2},
{3, 3, 3, 3, 3},
{4, 4, 4, 4, 4},
{5, 5, 5, 5, 5},
};
• Sample Output 1:
• 18 18 18
27 27 27
36 36 36

• Sample Input 2:
• n = 3, k = 2
• arr[][] = { {1, 2, 3},
{4, 5, 6},
{7, 8, 9},
};
• Sample Output 2:
• 12 16
24 28

## Code for finding sum of all sub-squares of size k x k in a n x n matrix

```// A simple C++ program to find sum of all subsquares of size k x k
#include
using namespace std;

// Size of given matrix
#define n 5

// A simple function to find sum of all sub-squares of size k x k
// in a given square matrix of size n x n
void printSumSimple (int mat[][n], int k)
{
// k must be smaller than or equal to n
if (k > n)
return;

// row number of first cell in current sub-square of size k x k
for (int i = 0; i < n - k + 1; i++)
{
// column of first cell in current sub-square of size k x k
for (int j = 0; j < n - k + 1; j++)
{
// Calculate and print sum of current sub-square
int sum = 0;
for (int p = i; p < k + i; p++)
for (int q = j; q < k + j; q++)
sum += mat[p][q];
cout << sum << " ";
}

// Line separator for sub-squares starting with next row
cout << endl;
}
}

// Driver program to test above function
int main ()
{
int mat[n][n] = { {1, 1, 1, 1, 1},
{2, 2, 2, 2, 2},
{3, 3, 3, 3, 3},
{4, 4, 4, 4, 4},
{5, 5, 5, 5, 5},
};
int k = 3;
printSumSimple (mat, k);
return 0;
}```
```Output

18 18 18
27 27 27
36 36 36```
```// A simple Java program to find sum of all
// subsquares of size k x k
class PI
{

// Size of given matrix
static final int n = 5;

// A simple function to find sum of all
//sub-squares of size k x k in a given
// square matrix of size n x n
static void printSumSimple (int mat[][], int k)
{

// k must be smaller than or
// equal to n
if (k > n)
return;

// row number of first cell in
// current sub-square of size k x k
for (int i = 0; i < n - k + 1; i++)
{

// column of first cell in current
// sub-square of size k x k
for (int j = 0; j < n - k + 1; j++)
{

// Calculate and print sum of
// current sub-square
int sum = 0;
for (int p = i; p < k + i; p++)
for (int q = j; q < k + j; q++)
sum += mat[p][q];

System.out.print (sum + " ");
}

// Line separator for sub-squares
// starting with next row
System.out.println ();
}
}

// Driver Program to test above function
public static void main (String arg[])
{
int mat[][] = { {1, 1, 1, 1, 1},
{2, 2, 2, 2, 2},
{3, 3, 3, 3, 3},
{4, 4, 4, 4, 4},
{5, 5, 5, 5, 5}
};
int k = 3;
printSumSimple (mat, k);
}
}```
```Output

18 18 18
27 27 27
36 36 36```

### 3 comments on “Question 3”

Can this be solved without using 4 nested loops?

• Mohd Saif

n=3
def sum_matrix(M,K):
if(K>n):
return
for i in range(n-K+1):
for j in range(n-K+1):
sum=0
for p in range(i,i+K):
for q in range(j,j+K):
sum=sum+M[p][q]
print(sum,end=” “)
print()
M=[[1,2,3],[4,5,6],[7,8,9]]
K=2
sum_matrix(M,K)