Formatted question description: https://leetcode.ca/all/861.html

# 861. Score After Flipping Matrix (Medium)

We have a two dimensional matrix A where each value is 0 or 1.

A move consists of choosing any row or column, and toggling each value in that row or column: changing all 0s to 1s, and all 1s to 0s.

After making any number of moves, every row of this matrix is interpreted as a binary number, and the score of the matrix is the sum of these numbers.

Return the highest possible score.

Example 1:

Input: [[0,0,1,1],[1,0,1,0],[1,1,0,0]]
Output: 39
Explanation:
Toggled to [[1,1,1,1],[1,0,0,1],[1,1,1,1]].
0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39

Note:

1. 1 <= A.length <= 20
2. 1 <= A.length <= 20
3. A[i][j] is 0 or 1.

Companies:
IIT Bombay

Related Topics:
Greedy

## Solution 1.

1. Makes sure the first column only contains 1s by toggling a row if the first element in the row is 0.
2. For the remaining columns, if there are more 0s than 1s, toggle the column.
// OJ: https://leetcode.com/problems/score-after-flipping-matrix/

// Time: O(MN)
// Space: O(1)
class Solution {
public:
int matrixScore(vector<vector<int>>& A) {
int M = A.size(), N = A.size(), ans = 0;
for (int i = 0; i < M; ++i) {
if (A[i]) continue;
for (int j = 0; j < N; ++j) A[i][j] = 1 - A[i][j];
}
for (int j = 1; j < N; ++j) {
int one = 0;
for (int i = 0; i < M; ++i) one += A[i][j];
if (one * 2 >= M) continue;
for (int i = 0; i < M; ++i) A[i][j] = 1 - A[i][j];
}
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) ans += A[i][j] * (1 << (N - j - 1));
}
return ans;
}
};


Java

class Solution {
public int matrixScore(int[][] A) {
int rows = A.length, columns = A.length;
for (int i = 0; i < rows; i++) {
if (A[i] == 0) {
for (int j = 0; j < columns; j++)
A[i][j] = 1 - A[i][j];
}
}
for (int i = 1; i < columns; i++) {
int ones = 0;
for (int j = 0; j < rows; j++)
ones += A[j][i];
if (ones < rows - ones) {
for (int j = 0; j < rows; j++)
A[j][i] = 1 - A[j][i];
}
}
int score = 0;
for (int i = 0; i < rows; i++) {
int[] row = A[i];
int curScore = 0;
for (int j = 0; j < columns; j++) {
curScore *= 2;
curScore += row[j];
}
score += curScore;
}
return score;
}
}