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
- 18 18 18
- Sample Input 2:
- n = 3, k = 2
- arr[][] = { {1, 2, 3},
{4, 5, 6},
{7, 8, 9},
};
- Sample Output 2:
- 12 16
24 28
- 12 16
Code for finding sum of all sub-squares of size k x k in a n x n matrix
C++
JAVA
C++
// 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
JAVA
// 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
Login/Signup to comment
n = int(input())
a, b = [], []
for i in range(n):
a.append(list(map(int, input().split())))
k = int(input())
for i in range(n – k + 1):
x, bb = a[i:i + k], []
for j in range(n – k + 1):
s = 0
for l in range(k):
s += sum(x[l][j:j + k])
bb.append(s)
b.append(bb)
for i in b:
for j in i:
print(j, end=” “)
print()