Question 1

33 comments on “Question 1”

• 
  

  SIDDHANT

  package TCS;

  import java.util.Scanner;

  public class Prog1 {
  public static void main(String[] args) {
  int M[][] = {{0, 1, 1, 0, 1},
  {1, 1, 0, 1, 0},
  {0, 1, 1, 1, 0},
  {1, 1, 1, 1, 0},
  {1, 1, 1, 1, 1},
  {0, 0, 0, 0, 0}};
  printArray(M);

  }

  static void printArray(int[][] M)
  {
  int max_of_s, max_i, max_j;
  int i,j;
  int R=M.length;
  int C= M[0].length;
  int S[][]=new int[R][C];

  //copy first row from M to S
  for(j=0;j<C;j++)
  {
  S[0][j]=M[0][j];
  }

  //copy first column from M to S
  for(i=1;i<R;i++)
  {
  S[i][0]=M[i][0];
  }

  //construct other entries of S
  for(i=1;i<R;i++)
  {
  for(j=1;j<C;j++)
  {
  if(M[i][j]==1)
  S[i][j] = Math.min(S[i][j-1],Math.min(S[i-1][j], S[i-1][j-1])) + 1;
  else if(M[i][j]==0)
  S[i][j]=0;
  }
  }

  /* Find the maximum entry, and indexes of maximum entry
  in S[][] */
  max_of_s = S[0][0]; max_i = 0; max_j = 0;
  for(i = 0; i < R; i++)
  {
  for(j = 0; j < C; j++)
  {
  if(max_of_s max_i – max_of_s; i–)
  {
  for(j = max_j; j > max_j – max_of_s; j–)
  {
  System.out.print(M[i][j] + ” “);
  }
  System.out.println();
  }
  }
  }

  Log in to Reply
• 
  

  Avirup

  #include
  using namespace std;

  int maxSubArray(int *arr1,int r,int c1)
  {
  int *sum=new int[r*c1];
  int s=1;
  for(int i=0;i<r;i++)
  {
  for(int j=0;j<c1;j++)
  {
  if(i==0||j==0)
  {
  sum[i*c1+j]=arr1[i*c1+j];
  }
  else
  {
  if(arr1[i*c1+j]==1)
  {
  int c=i-1;
  int d=j-1;
  sum[i*c1+j]=((sum[c*c1+d]<sum[i*c1+d])?((sum[c*c1+d]<sum[c*c1+j])?sum[c*c1+d]:sum[c*c1+j]):((sum[i*c1+d]s)
  s=sum[i*c1+j];
  }
  else
  {
  sum[i*c1+j]=0;
  }
  }
  }
  }
  return s;
  }
  int main()
  {
  int r,c,i,j;
  cin>>r>>c;
  int *arr=new int[r*c];
  for(i=0;i<r;i++)
  {
  for(j=0;j>arr[i*c+j];
  }
  }
  int s=maxSubArray(arr,r,c);
  for(i=0;i<s;i++)
  {
  for(j=0;j<s;j++)
  {
  cout<<"1 ";
  }
  cout<<"\n";
  }
  return 0;
  }

  Log in to Reply
• 
  

  Sudarshan

  // Maximum size square sub-matrix with all 1s

  #include
  #define bool int
  #define R 6
  #define C 5

  /* UTILITY FUNCTIONS */
  /* Function to get minimum of three values */
  int min(int a, int b, int c)
  {
  int m = a;
  if (m > b)
  m = b;
  if (m > c)
  m = c;
  return m;
  }

  void printMaxSubSquare(bool M[R][C])
  {
  int i, j;
  int S[R][C];
  int max_of_s, max_i, max_j;

  /* Set first column of S[][]*/
  for (i = 0; i < R; i++)
  S[i][0] = M[i][0];

  /* Set first row of S[][]*/
  for (j = 0; j < C; j++)
  S[0][j] = M[0][j];

  /* Construct other entries of S[][]*/
  for (i = 1; i < R; i++)
  {
  for (j = 1; j < C; j++)
  {
  if (M[i][j] == 1)
  S[i][j] = min(S[i][j – 1], S[i – 1][j], S[i – 1][j – 1]) + 1;
  else
  S[i][j] = 0;
  }
  }

  /* Find the maximum entry, and indexes of maximum entry
  in S[][] */
  max_of_s = S[0][0];
  max_i = 0;
  max_j = 0;
  for (i = 0; i < R; i++)
  {
  for (j = 0; j < C; j++)
  {
  if (max_of_s max_i – max_of_s; i–)
  {
  for (j = max_j; j > max_j – max_of_s; j–)
  {
  printf(“%d “, M[i][j]);
  }
  printf(“\n”);
  }
  }

  /* Driver function to test above functions */
  int main()
  {
  bool M[R][C] = {{1, 0, 0, 1, 0},
  {1, 1, 1, 1, 1},
  {1, 0, 1, 1, 1},
  {0, 0, 1, 1, 0},
  {1, 1, 1, 1, 1}};

  printMaxSubSquare(M);
  return 0;
  }

  Log in to Reply
• 
  

  Shubhadeep

  // JAVA Code for Maximum size square
  // sub-matrix with all 1s
  public class MaxSqMatrix {
  // method for Maximum size square sub-matrix with all 1s
  static void printMaxSubSquare(int M[][])
  {
  int i, j;
  int R = M.length; // no of rows in M[][]
  int C = M[0].length; // no of columns in M[][]
  int S[][] = new int[R][C];

  int max_of_s, max_i, max_j;

  /* Set first column of S[][]*/
  for (i = 0; i < R; i++)
  S[i][0] = M[i][0];

  /* Set first row of S[][]*/
  for (j = 0; j < C; j++)
  S[0][j] = M[0][j];

  /* Construct other entries of S[][]*/
  for (i = 1; i < R; i++) {
  for (j = 1; j < C; j++) {
  if (M[i][j] == 1)
  S[i][j] = Math.min(S[i][j – 1],
  Math.min(S[i – 1][j], S[i – 1][j – 1]))
  + 1;
  else
  S[i][j] = 0;
  }
  }

  /* Find the maximum entry, and indexes of maximum entry
  in S[][] */
  max_of_s = S[0][0];
  max_i = 0;
  max_j = 0;
  for (i = 0; i < R; i++) {
  for (j = 0; j < C; j++) {
  if (max_of_s max_i – max_of_s; i–) {
  for (j = max_j; j > max_j – max_of_s; j–) {
  System.out.print(M[i][j] + ” “);
  }
  System.out.println();
  }
  }

  // Driver program
  public static void main(String[] args)
  {
  int M[][] = { { 0, 1, 1, 0, 1 },
  { 1, 1, 0, 1, 0 },
  { 0, 1, 1, 1, 0 },
  { 1, 1, 1, 1, 0 },
  { 1, 1, 1, 1, 1 },
  { 0, 0, 0, 0, 0 } };

  printMaxSubSquare(M);
  }
  }

  Log in to Reply
• 
  

  Shruti

  public class Solution {
  public int solve(int[][] M) {
  int R= M.length;
  int C= M[0].length;
  int[][] S = new int[R][C];
  for(int j=0;j<C;j++){
  S[0][j]=M[0][j];
  }
  for(int i=0;i<R;i++){
  S[i][0]=M[i][0];
  }
  for(int i=1;i<R;i++){
  for(int j=1;j<C;j++){
  if(M[i][j]==0){
  S[i][j]=0;
  }
  else{
  int min= Math.min(S[i][j-1],Math.min(S[i-1][j],S[i-1][j-1]))+1;
  S[i][j]=min;
  }
  }
  }
  int largest= Integer.MIN_VALUE;
  for(int i=0;i<R;i++){
  for(int j=0;jlargest) largest= S[i][j];
  }
  }
  return largest*largest;
  }
  }

  Log in to Reply
• 
  

  Debparna

  import java.util.*;
  public class Main
  {
  public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
  String str = sc.nextLine();
  String li[] = str.split(” “);
  int R = Integer.parseInt(li[0]);
  int C = Integer.parseInt(li[1]);
  int arr[][] = new int[R][C];
  for(int i=0;i<R;i++){
  str = sc.nextLine();
  li = str.split(" ");
  for(int j=0;j<C;j++){
  arr[i][j] = Integer.parseInt(li[j]);
  }
  }

  int dp[][] = new int[R][C];
  for(int i=0;i<C;i++){
  dp[R-1][i] = arr[R-1][i];
  }
  for(int i=0;i=0;i–){
  for(int j=C-2;j>=0;j–){
  if(arr[i][j]==0){
  dp[i][j] = 0;
  }else{
  dp[i][j] = 1 + (dp[i][j+1]<dp[i+1][j]?
  (dp[i][j+1]<dp[i+1][j+1]?dp[i][j+1]:dp[i+1][j+1]):
  (dp[i+1][j] max){
  max = dp[i][j]; r = i; c=j;
  }
  }
  }
  for(int i=0;i<R;i++){
  for(int j=0;j<C;j++){
  System.out.print(dp[i][j]+" ");
  }
  System.out.println();
  }
  for(int i=r;i<r+max;i++){
  for(int j=c;j<c+max;j++){
  System.out.print(arr[i][j]+ " ");
  }
  System.out.println();
  }
  }
  }

  Log in to Reply
• 
  

  gaurav

  Java Solution:
  /******************************************************************************

  Online Java Compiler.
  Code, Compile, Run and Debug java program online.
  Write your code in this editor and press “Run” button to execute it.

  *******************************************************************************/
  import java.util.*;
  public class Main
  {
  public static void main(String[] args) {
  //Scanner sc = new Scanner(System.in);
  /*int M[][] = {{0, 1, 1, 0, 1},
  {1, 1, 0, 1, 0},
  {0, 1, 1, 1, 0},
  {1, 1, 1, 1, 0},
  {1, 1, 1, 1, 1},
  {0, 0, 0, 0, 0}};*/
  int M[][] = {{0, 1, 1, 0, 1},
  {0, 1, 1, 0, 0},
  {1, 1, 0, 0, 0},
  {1, 1, 1, 0, 1},
  {0, 0, 0, 0, 0}};
  printMaxSubSquare(M);
  }
  public static void printMaxSubSquare(int M[][]){
  int i,j;
  int R = M.length;
  int C = M[0].length;

  int s[][]=new int[R][C];
  for(i=0;i<R;i++)
  {
  s[i][0]=M[i][0];
  }
  for(j=0;j<C;j++)
  {
  s[0][j]=M[0][j];
  }

  for(i=1;i<R;i++){
  for(j=1;j<C;j++){
  if(M[i][j]==1)
  s[i][j]=Math.min((s[i-1][j]),Math.min(s[i][j-1],s[i-1][j-1]))+1;
  else
  s[i][j]=0;
  }
  }
  int max_c=0,max_r=0,max_of_s=s[0][0];
  for(i=0;i<R;i++){
  for(j=0;j<C;j++){
  if(max_of_smax_r-max_of_s;i–){
  for(j=max_c;j>max_c-max_of_s;j–){
  System.out.print(M[i][j]+” “);
  }
  System.out.println();
  }
  }
  }

  Log in to Reply
• 
  

  Shubham

  Python solution for this problem:
  def findSquareMatrix(M):
  s = [[0 for j in range(len(i))]for i in M]
  for i in range(len(M[0])):
  s[0][i] = M[0][i]
  for j in range(len(M)):
  s[j][0] = M[j][0]
  for i in range(1,len(M)):
  for j in range(1,len(M[i])):
  if(M[i][j] == 1):
  s[i][j] = min(s[i][j-1],s[i-1][j],s[i-1][j-1])+1
  else:
  s[i][j] = 0
  max_s = s[0][0]
  max_i = 0
  max_j = 0
  for i in range(len(M)):
  for j in range(len(M[0])):
  if(max_s<s[i][j]):
  max_s = s[i][j]
  max_i = i
  max_j = j
  for i in range(max_i,max_i-max_s,-1):
  for j in range(max_j,max_j-max_s,-1):
  print(M[i][j],end = ' ')
  print()

  n = int(input("Enter number of rows and columns: "))
  matrix = []
  for i in range(n):
  matrix.append(list(map(int,input().strip().split())))
  findSquareMatrix(matrix)

  Log in to Reply
• 
  

  Yokesh Rana

  Java Solution For this problem
  package test;

  import java.util.Scanner;

  public class max_size_subarray {
  static int[][] t;
  public static void main(String[] args) {
  Scanner sc=new Scanner(System.in);
  int x=sc.nextInt(),y=sc.nextInt();

  int[][] a=new int[x][y];

  for(int i=0;i<x;i++) {
  for(int j=0;j<y;j++) {
  a[i][j]=sc.nextInt();
  }
  }
  t=new int[x][y];
  int max=-1;
  for(int i=0;i<x;i++)
  for(int j=0;jmax)
  max=t[i][j];
  }
  System.out.println(max+1);
  }

  private static int maxsizesubaary_matrix(int[][] a, int i, int j, int x, int y) {
  if(i==x-1||j==y-1)
  return t[i][j];
  if(a[i][j+1]==1&&a[i+1][j]==1&&a[i+1][j+1]==1) {
  if(t[i+1][j+1]==0)
  t[i][j]=1+maxsizesubaary_matrix(a, i+1, j+1,x,y);
  else
  t[i][j]=1+t[i+1][j+1];
  }
  return t[i][j];
  }
  }

  Log in to Reply
• 
  

  Bakwas Insaan

  My dp solution
  import java.io.*;
  import java.util.*;
  class problem2{
  public static void main(String[] args){
  Scanner s= new Scanner(System.in);
  int m= s.nextInt();
  int n= s.nextInt();
  int[][] mat= new int[m][n];
  for(int i= 0;i<m;i++){
  for(int j= 0;j<n;j++){
  mat[i][j]= s.nextInt();
  }
  }
  int[][] dp= new int[m+1][n+1];
  for(int i= 0;i<m;i++){
  dp[i][0]= 0;
  }
  for(int i= 0;i<n;i++){
  dp[0][i]= 0;
  }
  for(int i=1;i<=m;i++){
  for(int j=1;j<=n;j++){
  if(mat[i-1][j-1]==1){
  dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1;
  }
  }
  }
  int max=Integer.MIN_VALUE;
  for(int i=0;i<=m;i++){
  for(int j=0;j<=n;j++){
  if(max<dp[i][j]){
  max=dp[i][j];
  }

  }

  }
  System.out.println(max);

  }
  public static int min(int a,int b,int c){
  if(a<b){
  if(a<c){
  return a;
  }
  else{
  return c;
  }
  }
  else{
  return b;
  }

  }
  }

  Log in to Reply
• 
  

  varaprasad koluboyina

  this is my code in java
  package test;
  import java.util.Scanner;
  public class tcs {
  int [][]arr;
  int row,column;
  int max;
  tcs()
  {
  Scanner scan=new Scanner(System.in);
  row=scan.nextInt();
  column=scan.nextInt();
  arr=new int[row][column];
  for(int i=0;i<row;i++)
  {
  for(int j=0;j<column;j++)
  {
  arr[i][j]=scan.nextInt();
  }
  }
  max=0;
  }
  void summer(int i,int j)
  {

  int flag=1;
  int sum;
  while(flag<=column-j)
  {

  sum=0;
  for(int k=i;k<flag+i;k++)
  {
  for(int l=j;l<flag+j;l++)
  {
  sum+=arr[k][l];
  }

  }
  if(sum==(flag*flag))
  {
  if(max<flag) max=flag;
  flag++;
  }
  else
  {
  return;
  }
  }
  }
  void calc()
  {
  for(int i=0;i<(row-max);i++)
  {
  for(int j=0;j<column-max;j++)
  {
  if(arr[i][j]==1)
  {
  summer(i,j);
  }
  }
  }
  }
  public static void main(String []args)
  {
  tcs t=new tcs();
  t.calc();
  System.out.println(t.max);
  }
  }

  Log in to Reply
• 
  

  Shivangi Mishra

  is it mandatory to code in c/c++or java??can’t we use python?

  Log in to Reply
• 
  

  Prep Insta

  You can use python as well.

  Log in to Reply
• 
  

  Geetha

  matrix=[]
  a=[]
  n=int(input())
  for _ in range(n):
  matrix.append(list(map(int,input().split())))
  for i in matrix:
  a.append(i.count(1))
  print([[1]*a[0]]*n)

  Log in to Reply