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.

Example :

  • Input :arr[3][3] = {(1,0, 0), (0, 0, 0), (1, 1, 1)}
  • Output : 2
Row with maximum number of 1's in C++
While loop in C

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)
Row with maximum numbers

Code to find row with maximum number of 1's in C++

Run 
#include<bits/stdc++.h>
using namespace std;

int main(){

   bool 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;
     }
   }

   cout << "Index of row with maximum 1s is " << index;

}

Output :

Index of row with maximum 1's is 2
While loop in C

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)

Code to find row with maximum number of 1's in C++

Run 
#include<bits/stdc++.h>
using namespace std;

int first(bool 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(){

   bool 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;
     }
   }

   cout << "Index of row with maximum 1s is " << index;

}

Output :

Index of row with maximum 1's is 2