# Maximize score of Binary Matrix by Flipping a row or column each time

*
*

*
*Given a ** Binary matrix** of size

**, the task is to maximize the score of Matrix by making any number of moves (including zero moves), such that,**

**MxN**- every row is interpreted as a Binary Number, and
- the score of the matrix is the sum of these binary numbers.
- A move is defined as choosing any row or column and toggling/flipping each value in that row or column (i.e., toggling all 0’s to 1’s, and visa-versa).

**Examples:**

grid = [[0,1,1,1],Input:

[1,0,0,0],

[1,1,0,0]]

41Output:

After making moves as shown in the image below, the final score will be 1111 + 1111 + 1011 = 15 + 15 + 11 = 41.Explanation:

grid = [[0]]Input:1Output:0b1 = 1.Explanation:

** Approach: **We can solve this problem optimally using the idea that

So we will make grid[i][0] = 1 for every row [ i=0…n-1].To make value large its MSB should always be ‘1’.

- Now we will traverse from left to right and check for every column for the count of 1’s and 0’s and if any point we have no. of 0’s greater than 1’s we will toggle that column to make 1’s >= 0’s .
- In the end, we will calculate the final score.

Below is the implementation of the above approach :

## C++

// C++ implimentation of above idea #include <bits/stdc++.h> using namespace std; // function to toggle the whole column void flipCol(int col, vector<vector<int> >& grid) { for (int j = 0; j < grid.size(); j++) { grid[j][col] ^= 1; } } // function to toggle the whole row void flipRow(int row, vector<vector<int> >& grid) { for (int i = 0; i < grid[0].size(); i++) { grid[row][i] ^= 1; } } int matrixScore(vector<vector<int> >& grid) { int n = grid.size(); int m = grid[0].size(); // MSB should be 1 of 0th column // to get the maximum value for (int i = 0; i < n; i++) { if (grid[i][0] == 0) { flipRow(i, grid); } } // cheacking which column has more 0's than 1's // and toggling them. for (int j = 0; j < m; j++) { int zeros = 0; for (int i = 0; i < n; i++) { if (grid[i][j] == 0) zeros++; } if (zeros > (n - zeros)) { flipCol(j, grid); } } // Calculate the answer int sum = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (grid[i][j]) { sum += (1LL << (m - j - 1)); } } } return sum; } // Driver Code int main() { int n, m; n = 3; m = 4; vector<vector<int> > grid = { { 0, 1, 1, 1 }, { 1, 0, 0, 0 }, { 1, 1, 0, 0 } }; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> grid[i][j]; } } cout << "Maximum Value : " << matrixScore(grid) << endl; }

** Time Complexity: **O(N*M)

** Auxiliary Space Complexity: **O(1)