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 < m; i++ {
if grid[i][0] == 0 {
for j := 0; j < n; j++ {
grid[i][j] ^= 1
}
}
}
ans := 0
for j := 0; j < n; j++ {
cnt := 0
for i := 0; i < m; i++ {
cnt += grid[i][j]
}
if cnt < m-cnt {
cnt = m - cnt
}
ans += 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 | function matrixScore(grid: number[][]): number {
const m = grid.length;
const n = grid[0].length;
for (let i = 0; i < m; ++i) {
if (grid[i][0] == 0) {
for (let j = 0; j < n; ++j) {
grid[i][j] ^= 1;
}
}
}
let ans = 0;
for (let j = 0; j < n; ++j) {
let cnt = 0;
for (let 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
23 | public 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) {
if (grid[i][j] == 1) {
++cnt;
}
}
ans += Math.Max(cnt, m - cnt) * (1 << (n - j - 1));
}
return ans;
}
}
|