Thursday, 27 August 2015

Count the Number of 1’s in each row

Count the Number of 1’s in each row:

Given a boolean matrix with every row sorted, find the row with maximum number of 1s.



package core.geeks;
import java.io.PrintStream;
public class MaxNum1SortedMatrix {
       static PrintStream out = java.lang.System.out;
       public static void main(String[] args) {
              int[][] sortedMatrix = {{0,0,0,1,1,1},
                                                       {0,0,1,1,1,1},
                                                       {0,0,0,0,1,1},
                                                       {1,1,1,1,1,1},
                                                       {0,0,1,1,1,1}};
              int row = sortedMatrix.length-1;
              int column = sortedMatrix[0].length-1;
              int[] resultArr = new int[row+1];
             
              for (int i = 0; i <=row; i++) {
                     int[] temp = sortedMatrix[i];
                     resultArr[i] = column - binarySerachIdx(temp)+1;
              }
             
              for (int i = 0; i < resultArr.length; i++) {
                     System.out.println(resultArr[i]);
              }
       }

       private static int binarySerachIdx(int[] temp) {
              int start = 0; int mid = temp.length/2;
              while(start<mid) {
                     if(temp[mid]==1 && mid>0 && temp[mid-1]==1) {
                           mid = mid-1;
                          
                     } else if(temp[mid]==0 && mid<temp.length) {
                           start = mid;
                           mid = temp.length-1;
                     } else {
                           return mid;
                     }
              }
              return 0;
       }
}
Output:
3
4
2
6
4



No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...