Find Row with maximum number of 1’s in C

April 30, 2022

Row with maximum number of 1’s in C

Here, in this page we will discuss the program to find the row with maximum number of 1’s in C Programming Language. We are given with an two dimensional array, containing only 0 and 1, each row of the matrix are sorted. We need to print the index of that row, which contain maximum number of 1’s.

Method 1 :

Take a variable to hold the index value of required row, let it be index=-1, and max_count=0, that hold the maximum count of 1.
Now, iterate over each row, and take variable say count=0, to count the number of 1’s in current row.
For, i-th row, iterate over the columns and increase the value of count if element is equal to 1.
Check if count > max_count, then set max_count = count and index=i.
After the iteration of each row, print the value of index.

Time and Space Complexity :

Time-Complexity : O(r*c)
Space-Complexity : O(1)

Method 1 : Code in C

Run

#include <stdio.h>

int main(){

   int mat[4][4] = {{0, 0, 0, 1}, 
                    {0, 1, 1, 1}, 
                    {1, 1, 1, 1}, 
                    {0, 0, 0, 0}};

   int max_count=0, index=-1;

   for(int i=0; i<4; i++){
     int count = 0;
     for(int j=0; j<4; j++){ 
         if(mat[i][j]==1) 
            count++; 
         
     } 
     if(count>max_count)
     {
        max_count = count;
        index = i;
     }
   }

   printf("Index of row with maximum 1s is %d", index);

}

Output :

Index of row with maximum 1's is 2

Method 2 (Using Binary Search) :

Take a variable to hold the index value of required row, let it be index=-1, and max_count=0, that hold the maximum count of 1.
Now, iterate over each row, and take variable say count=0, to count the number of 1’s in current row.
For, i-th row, use binary search to find the first instance of 1.
Then count = No. of columns – first instance of 1.
Check if count > max_count, then set max_count = count and index=i.
After the iteration of all rows, print the value of index.

Time and Space Complexity :

Time-Complexity : O(r*log(c))
Space-Complexity : O(1)

Method 2 : Code in C

Run

#include <stdio.h>

int first(int arr[], int low, int high)
{
    if(high >= low)
    {
      int mid = low + (high - low)/2;
      if ( ( mid == 0 || arr[mid-1] == 0) && arr[mid] == 1)
        return mid;

      else if (arr[mid] == 0)
        return first(arr, (mid + 1), high);

      else
        return first(arr, low, (mid -1));
     }
     return -1;
}


int main(){

   int mat[4][4] = {{0, 0, 0, 1}, 
                    {0, 1, 1, 1}, 
                    {1, 1, 1, 1}, 
                    {0, 0, 0, 0}};

   int max_count=0, index=-1;

   for(int i=0; i<4; i++){ int count = 0; int x = first(mat[i], 0, 3); if(x!=-1) count = 4-x; if(count>max_count){
                max_count = count;
                index = i;
     }
   }

   printf("Index of row with maximum 1s is %d", index);

}

Output :

Index of row with maximum 1's is 2