Description
You are given an m x n
binary matrix grid
.
A move consists of choosing any row or column and toggling each value in that row or column (i.e., changing all 0
's to 1
's, and all 1
's to 0
's).
Every row of the matrix is interpreted as a binary number, and the score of the matrix is the sum of these numbers.
Return the highest possible score after making any number of moves (including zero moves).
Example 1:
Input: grid = [[0,0,1,1],[1,0,1,0],[1,1,0,0]]
Output: 39
Explanation: 0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39
Example 2:
Input: grid = [[0]]
Output: 1
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 20
grid[i][j]
is either 0
or 1
.
Solutions
Solution 1
1
2
3
4
5
6
7
8
9
10
11
12 | class Solution:
def matrixScore(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
for i in range(m):
if grid[i][0] == 0:
for j in range(n):
grid[i][j] ^= 1
ans = 0
for j in range(n):
cnt = sum(grid[i][j] for i in range(m))
ans += max(cnt, m - cnt) * (1 << (n - j - 1))
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | class Solution {
public int matrixScore(int[][] grid) {
int m = grid.length, n = grid[0].length;
for (int i = 0; i < m; ++i) {
if (grid[i][0] == 0) {
for (int j = 0; j < n; ++j) {
grid[i][j] ^= 1;
}
}
}
int ans = 0;
for (int j = 0; j < n; ++j) {
int cnt = 0;
for (int i = 0; i < m; ++i) {
cnt += grid[i][j];
}
ans += Math.max(cnt, m - cnt) * (1 << (n - j - 1));
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | class Solution {
public:
int matrixScore(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
for (int i = 0; i < m; ++i) {
if (grid[i][0] == 0) {
for (int j = 0; j < n; ++j) {
grid[i][j] ^= 1;
}
}
}
int ans = 0;
for (int j = 0; j < n; ++j) {
int cnt = 0;
for (int i = 0; i < m; ++i) {
cnt += grid[i][j];
}
ans += max(cnt, m - cnt) * (1 << (n - j - 1));
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | func matrixScore(grid [][]int) int {
m, n := len(grid), len(grid[0])
for i := 0; i
|