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
Rationalization: After making strikes as proven within the picture under, the ultimate rating will probably be 1111 + 1111 + 1011 = 15 + 15 + 11 = 41.
Enter: grid = [[0]]
Output: 1
Rationalization: 0b1 = 1.
.png)
Method: We will remedy this downside optimally utilizing the concept that
To make worth giant its MSB ought to all the time be ‘1’. So we’ll make grid[i][0] = 1 for each row [ i=0…n-1].
- Now we’ll traverse from left to proper and examine for each column for the rely of 1’s and 0’s and if any level we’ve no. of 0’s higher than 1’s we’ll toggle that column to make 1’s >= 0’s .
- Ultimately, we’ll calculate the ultimate rating.
Under is the implementation of the above method :
C++
// C++ implimentation of above concept
#embody <bits/stdc++.h>
utilizing namespace std;
// operate 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;
}
}
// operate 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 primary()
{
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)
RelatedPosts
