Given a Binary matrix of size MxN, the task is to maximize the score of Matrix by making any number of moves (including zero moves), such that,
- 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:
Input: grid = [[0,1,1,1],
[1,0,0,0],
[1,1,0,0]]Output: 41
Explanation: After making moves as shown in the image below, the final score will be 1111 + 1111 + 1011 = 15 + 15 + 11 = 41.
Input: grid = [[0]]
Output: 1
Explanation: 0b1 = 1.
Approach: We can solve this problem optimally using the idea that
To make value large its MSB should always be ‘1’. So we will make grid[i][0] = 1 for every row [ i=0…n-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)
Given a Binary matrix of size MxN, the task is to maximize the score of Matrix by making any number of moves (including zero moves), such that,
- 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:
Input: grid = [[0,1,1,1],
[1,0,0,0],
[1,1,0,0]]Output: 41
Explanation: After making moves as shown in the image below, the final score will be 1111 + 1111 + 1011 = 15 + 15 + 11 = 41.
Input: grid = [[0]]
Output: 1
Explanation: 0b1 = 1.
Approach: We can solve this problem optimally using the idea that
To make value large its MSB should always be ‘1’. So we will make grid[i][0] = 1 for every row [ i=0…n-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)