Question 3

September 8, 2020

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

14 comments on “Question 3”


  • 4PS20EC420

    import numpy as np
    def hi(a,k):
    a1=[]
    l=len(a)
    if l<k:
    return 0
    for i in range(l-k+1):
    for j in range(l-k+1):
    s=0
    for p in range(i,i+k):
    for q in range(j,j+k):
    s+=a[p][q]
    a1.append(s)
    return a1

    n=int(input("size"))
    k=int(input("sub"))
    l=list(map(int,input().strip().split(',')))[:n*n]
    a=np.array(l)
    a=a.reshape(n,n)
    print(a)
    a1=hi(a,k)
    a1=np.array(a1)
    a1=a1.reshape(k,k)
    print(a1)


  • culbgaming12

    #include

    using namespace std;

    int main()
    {
    int n;
    cin >> n;
    int arr[n][n];

    int k;
    cin >> k;

    for (int i = 0; i < n; i++)
    {
    for (int j = 0; j > arr[i][j];
    }
    }

    int row = n;
    int col = n;

    int dp[row + 1][col + 1];

    for (int i = 0; i < n; i++)
    {
    dp[0][i] = 0;
    dp[i][0] = 0;
    }

    for (int i = 1; i <= row; i++)
    {
    for (int j = 1; j <= col; j++)
    {
    dp[i][j] = arr[i – 1][j – 1] + dp[i – 1][j] + dp[i][j – 1] – dp[i – 1][j – 1];
    }
    }
    int sum;
    for (int i = 1; i <= row; i++)
    {
    for (int j = 1; j = 0 && j – k >= 0)
    {
    sum = dp[i][j] – dp[i – k][j] – dp[i][j – k] + dp[i – k][j – k];

    cout << sum << " ";
    }
    }

    cout << endl;
    }

    return 0;
    }


  • Tathagata

    PIJUSH #DP_
    #include
    using namespace std;

    int main()
    {
    int row=5;
    int col=5;

    int A[row][col] = {{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 B= 3;

    int dp[row+1][col+1];
    for(int i=0;i<row+1;i++){
    dp[i][0]=0;
    }
    for(int i=0;i<col+1;i++){
    dp[0][i]=0;
    }
    for(int i=1;i<=row;i++){
    for(int j=1;j<=col;j++){
    dp[i][j]=A[i-1][j-1]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];
    }
    }
    int sum=0;
    for(int i=1;i<=row;i++){
    for(int j=1;j=0 && j-B>=0){

    sum=dp[i][j]-dp[i-B][j]-dp[i][j-B]+dp[i-B][j-B];
    cout<<sum<<" ";

    }
    }
    cout<<endl;
    }

    return 0;
    }


  • sandeep

    Python code:
    def sum_matrix(arr,k):
    l = len(arr)
    #new =[k][k]
    if l<k:
    return 0
    for i in range(l-k+1):
    for j in range(l-k+1):
    sum =0
    for p in range(i,k+i):
    for q in range(j,k+j):
    sum+=arr[p][q]
    print(sum,end =" ")
    print("\n")

    if __name__ == '__main__':
    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]]
    k = int(input())
    sum_matrix(arr,k)


  • Gourav

    s1=[[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]]
    #Gourav Raghuwanshi
    k=3
    dp=[[0 for i in range (len(s1[0])+1)] for i in range (len(s1)+1)]
    for i in range (1,len(s1)+1):
    for j in range (1,len(s1[0])+1):
    dp[i][j]=s1[i-1][j-1]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]

    ”’
    dp=[[0, 0, 0, 0, 0, 0], dp= [-2,12] by dp—-> 16-5-7+3=7 s1=[-2,8]
    [0, 3, -1, 5, 0, 1], [-7,16] by s1—-> -2+8-2+9=7 [-8,9]
    [0, 4, -2, 12, 3, 2],
    [0, 7, -7, 16, 10, 10],
    [0, 0, -11, 16, 12, 19],
    [0, -3, -7, 15, 18, 19]]
    ”’
    dp1=[[0 for i in range (k)] for i in range (k)]
    maxsum=0
    curr=0
    for i in range (1,len(s1)+1):
    for j in range (1,len(s1[0])+1):
    if(i-1+k<=len(s1) and j-1+kmaxsum):
    maxsum=curr
    xco = (i-1,i-1+k)
    yco = (j-1,j-1+k)
    print(dp1)

    #print(dp)


  • Shahla

    #include
    using namespace std;

    int main() {
    int n;
    cin>>n;
    int mat[n][n];

    for(int i=0; i<n; i++)
    {
    for(int j=0;j>mat[i][j];
    }

    int k;
    cin>>k;

    int sum[n][n];

    for(int j=0 ; j<n ;j++)
    {
    int s=0;
    for(int i=0;i<k ;i++)s+= mat[i][j];

    sum[0][j]=s;

    for(int i=1; i<n-k+1; i++)
    {
    s+= mat[i+k-1][j]-mat[i-1][j];
    sum[i][j]=s;
    }
    }

    int finalsum=0;
    for(int i=0; i<n-k+1; i++)
    {
    int s=0;
    for(int j=0;j<k ;j++)s+= sum[i][j];

    finalsum+=s;
    cout<<s<<" ";

    for(int j=1; j<n-k+1; j++)
    {
    s+= sum[i][j+k-1]-sum[i][j-1];
    finalsum+=s;
    cout<<s<<" ";
    }
    cout<<endl;

    }

    //cout<<finalsum<<endl;

    return 0;
    }


  • SAYAN

    Solution in JAVA:
    import java.util.Scanner;

    public class SumOfSubSquareMatrixFromParentMatrix {

    public static void main(String[] args) {
    // TODO Auto-generated method stub
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt(), k = sc.nextInt(), sum = 0, posi = 0, posj = 0;
    int arr[][] = new int[n][n];
    for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
    arr[i][j] = sc.nextInt();
    }
    }
    while(posi + k <= n) {
    while(posj + k <= n) {
    for(int i = posi; i < posi + k; i++) {
    for(int j = posj; j < posj + k; j++) {
    sum = sum + arr[i][j];
    }
    }
    System.out.print(sum + " ");
    sum = 0;
    posj++;
    }
    System.out.println();
    posi++;
    posj = 0;
    }

    }

    }


  • Giridhar

    def matSum(i,j,mat,n,m,k):
    if i+k>n or j+k>m:
    return 0
    else:
    lis2=[]
    for x in range(i,i+k):
    for y in range(j,j+k):
    lis2.append(mat[x][y])

    return sum(lis2)

    n,m=map(int,input().split())
    k=int(input())
    Mat=[]
    for i in range(n):
    Mat.append(list(map(int,input().split()[:m])))

    lis1=[[0 for a in range(n)]for b in range(m)]
    for i in range(0,n):
    for j in range(0,m):
    lis1[i][j]=matSum(i,j,Mat,n,m,k)

    print()

    lis=[[0 for a in range(n+1-k)]for b in range(m+1-k)]

    for i in range(n+1-k):
    for j in range(m+1-k):
    lis[i][j]=lis1[i][j]

    for i in lis:
    for j in i:
    print(j,end=’ ‘)
    print()


  • Debjit

    #include

    int main()
    {
    int n,k,i,j,a[100][100],b[100][100],m,l,sum=0;
    scanf(“%d”,&n);
    scanf(“%d”,&k);

    for(i=0;i<n;i++)
    {
    for(j=0;j<n;j++)
    {
    scanf("%d",&a[i][j]);
    }
    }

    for(m=0;m<k;m++)
    {
    for(l=0;l<k;l++)
    {
    for(i=m;i<m+k;i++)
    {
    for(j=l;j<l+k;j++)
    {
    sum=sum+a[i][j];
    }
    }
    b[m][l]=sum;
    sum=0;
    }
    }

    for(m=0;m<k;m++)
    {
    for(l=0;l<k;l++)
    {
    printf("%d ",b[m][l]);
    }
    printf("\n");
    }
    }


  • Sayoni

    #include

    int main()
    {
    int n,k,i,j,x,y,a[100][100],sum=0;
    scanf(“%d”,&n);
    scanf(“%d”,&k);
    for(i=0;i<n;i++)
    {
    for(j=0;j<n;j++)
    {
    scanf("%d",&a[i][j]);
    }
    }
    for(i=0;i<n;i++)
    {
    for(j=0;j<n;j++)
    {
    printf("%d ",a[i][j]);
    }
    printf("\n");
    }
    for(y=0;y<k;y++)
    {
    for(x=0;x<k;x++)
    {
    sum=0;
    for(i=y;i<y+k;i++)
    {
    for(j=x;j<x+k;j++)
    {
    sum=sum+a[i][j];
    }
    }
    printf("%d ",sum);
    }
    printf("\n");
    }
    }


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

1 2