# Find Row with Maximum Number of 1’s in C++

## 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

## 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)

## 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`

## 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`