Submatrix - Unit Digit Corner
Submatrix - Unit Digit Corner
PROBLEM STATEMENT :
The program must accept an integer matrix of size R*C and a digit D as the input. The program must print the 3*3 submatrix having the maximum sum and the unit digit of the bottom-right corner element as D. If two or more such submatrices have the same maximum sum, then the program must print the first occurring submatrix as the output. If there is no such submatrix, the program must print -1 as the output.
Boundary Condition(s):
3 <= R, C <= 50
1 <= Matrix element value <= 1000
0 <= D <= 9
Input Format:
The first line contains R and C separated by a space.
The next R lines, each contains C integer values separated by a space.
The (R+2)th line contains D.
Output Format:
The first line contains -1 or the lines contain the first occurring submatrix.
Example Input/Output 1:
Input: ()
4 5
35 24 42 17 37
24 13 35 18 39
16 10 26 25 23
35 29 13 11 18
3
Output:
42 17 37
35 18 39
26 25 23
Explanation:
Here R = 4, C = 5 and D = 3.
There are two 3*3 submatrices having 3 as the unit digit of the bottom-right corner element.
The sum of the below 3*3 submatrix is 262.
35 18 39
26 25 23
The sum of the below 3*3 submatrix is 201.
16 10 26
35 29 13
The submatrix with the maximum sum is printed as the output.
Example Input/Output 2:
Input: ()
4 4
43 32 23 29
11 11 21 20
28 50 18 15
47 14 14 42
1
Output:
-1
1) LEARN THRICE
👇
2) THINK TWICE
👇
3) APPLY ONCE
SOLUTION :
C (Programming Language)
#include<stdio.h>
#include<stdlib.h>
int main()
{
int R,C;
scanf("%d %d",&R,&C);
int matrix[R][C];
for(int i=0;i<R;i++)
{
for(int j=0;j<C;j++)
{
scanf("%d ",&matrix[i][j]);
}
}
int unitDigit,maxSum=0,startRow,startCol,flag=0;
scanf("%d",&unitDigit);
for(int i=0;i<=R-3;i++)
{
for(int j=0;j<=C-3;j++)
{
int sum=0;
if(matrix[i+2][j+2]%10==unitDigit)
{
flag=1;
for(int row=i;row<3+i;row++)
{
for(int col=j;col<3+j;col++)
{
sum+=matrix[row][col];
}
}
}
if(sum>maxSum)
{
startRow=i;startCol=j;
maxSum=sum;
}
}
}
if(flag==0)
{
printf("-1");
return 0;
}
for(int i=startRow;i<3+startRow;i++)
{
for(int j=startCol;j<3+startCol;j++)
{
printf("%d ",matrix[i][j]);
}
printf("\n");
}
}
C++ (CPP)
#include <bits/stdc++.h>
using namespace std;
int main(int argc, char** argv)
{
int r,c,i,j,mat[50][50],d,maxi=0,start,end,sum,k,l;
cin>>r>>c;
for(i=0;i<r;i++)
{
for(j=0;j<c;j++)
{
cin>>mat[i][j];
}
}
cin>>d;
for(i=2;i<r;i++)
{
for(j=2;j<c;j++)
{
if(mat[i][j]%10==d)
{
sum=0;
for(k=i-2;k<=i;k++)
{
for(l=j-2;l<=j;l++)
{
sum+=mat[k][l];
}
}
if(maxi<sum)
{
maxi=sum;
start=i-2;
end=j-2;
}
}
}
}
if(maxi==0)
{
cout<<"-1";
return 0;
}
for(i=start;i<start+3;i++)
{
for(j=end;j<end+3;j++)
{
cout<<mat[i][j]<<" ";
}
cout<<"\n";
}
}
JAVA
import java.util.*;
public class Hello {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int R=sc.nextInt(),C=sc.nextInt();
int[][] matrix=new int[R][C];
for(int row=0;row<R;row++){
for(int col=0;col<C;col++){
matrix[row][col]=sc.nextInt();
}
}
int D=sc.nextInt(),maxSum=-100,subRow=-1,subCol=-1;
for(int row=0;row<=R-3;row++){
for(int col=0;col<=C-3;col++){
if(matrix[row+2][col+2]%10!=D){
continue;
}
int sum=0;
for(int sRow=row;sRow<row+3;sRow++){
for(int sCol=col;sCol<col+3;sCol++){
sum+=matrix[sRow][sCol];
}
}
if(sum>maxSum){
maxSum=sum;
subRow=row;
subCol=col;
}
}
}
if(subRow==-1){
System.out.print("-1");
}
else
{
for(int row=subRow;row<subRow+3;row++){
for(int col=subCol;col<subCol+3;col++){
System.out.print(matrix[row][col]+" ");
}
System.out.print("\n");
}
}
}
}
PYTHON
r,c=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(r)]
d=int(input())
m=0;x=-1
for i in range(r-2):
for j in range(c-2):
s=sum([sum(l[i1][j:j+3]) for i1 in range(i,i+3)])
if l[i+2][j+2]%10==d and s>m:
m=s
x=[l[i1][j:j+3] for i1 in range(i,i+3)]
if x==-1:
print(x)
quit()
for i in x:
print(*i)
Comments
Post a Comment