Given a Binary matrix of dimension MxN, the duty is to maximise the rating of Matrix by making any variety of strikes (together with zero strikes), such that,
- each row is interpreted as a Binary Quantity, and
- the rating of the matrix is the sum of those binary numbers.
- A transfer is outlined as selecting any row or column and toggling/flipping every worth in that row or column (i.e., toggling all 0’s to 1’s, and visa-versa).
Examples:
Enter: grid = [[0,1,1,1],
[1,0,0,0],
[1,1,0,0]]Output: 41
Clarification: After making strikes as proven within the picture beneath, the ultimate rating shall be 1111 + 1111 + 1011 = 15 + 15 + 11 = 41.
Enter: grid = [[0]]
Output: 1
Clarification: 0b1 = 1.
.png)
Strategy: We are able to resolve this downside optimally utilizing the concept
To make worth massive its MSB ought to at all times be ‘1’. So we are going to make grid[i][0] = 1 for each row [ i=0…n-1].
- Now we are going to traverse from left to proper and verify for each column for the depend of 1’s and 0’s and if any level we’ve no. of 0’s better than 1’s we are going to toggle that column to make 1’s >= 0’s .
- Ultimately, we are going to calculate the ultimate rating.
Under is the implementation of the above strategy :
C++
// C++ implimentation of above concept
#embody <bits/stdc++.h>
utilizing namespace std;
// perform to toggle the entire column
void flipCol(int col, vector<vector<int> >& grid)
{
for (int j = 0; j < grid.dimension(); j++) {
grid[j][col] ^= 1;
}
}
// perform to toggle the entire row
void flipRow(int row, vector<vector<int> >& grid)
{
for (int i = 0; i < grid[0].dimension(); i++) {
grid[row][i] ^= 1;
}
}
int matrixScore(vector<vector<int> >& grid)
{
int n = grid.dimension();
int m = grid[0].dimension();
// MSB ought to be 1 of 0th column
// to get the utmost worth
for (int i = 0; i < n; i++) {
if (grid[i][0] == 0) {
flipRow(i, grid);
}
}
// cheacking which column has extra 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 reply
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 principal()
{
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 << "Most Worth : " << matrixScore(grid) << endl;
}
Time Complexity: O(N*M)
Auxiliary Area Complexity: O(1)
