Question 3

code for finding 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

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”


  • 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)