Sponsored
Sponsored
To maximize the score, we should ensure that the leftmost bit (most significant bit) of each binary number (row) is 1. If the first bit of any row is 0, we can flip that entire row.
Once the leading bits are all 1, we maximize further by toggling columns where the count of 0s is more than 1s. This ensures that the binary numbers are as large as possible.
Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the grid. Space Complexity: O(1), using inplace modifications.
1#include <stdio.h>
2#include <math.h>
3
4int matrixScore(int** grid, int gridSize, int* gridColSize) {
5 int m = gridSize;
6 int n = gridColSize[0];
7 int score = 0;
8
9 // Step 1: Ensure the first column is all ones
10 for (int i = 0; i < m; ++i) {
11 if (grid[i][0] == 0) {
12 for (int j = 0; j < n; ++j) {
13 grid[i][j] ^= 1;
14 }
15 }
16 }
17
18 // Step 2: For each column (except the first), maximize the number of 1s
19 for (int j = 0; j < n; ++j) {
20 int colCount = 0;
21 for (int i = 0; i < m; ++i) {
22 if (grid[i][j] == 1) {
23 colCount++;
24 }
25 }
26 colCount = fmax(colCount, m - colCount);
27 score += colCount * (1 << (n - j - 1));
28 }
29
30 return score;
31}The C solution uses a two-step approach. First, it ensures the first column is all 1s by flipping rows if needed. Then, it checks each column from the second to maximize the count of 1s, flipping the column if 0s are more frequent.
This approach differs slightly by treating the majority of 1s per column as more influential. Instead of flipping rows first, the solution primarily ensures maximal 1 presence per column, beginning with the columns themselves.
Time Complexity: O(m * n), as each element in the matrix grid is visited once. Space Complexity: O(1), operating in-place.
1public class Solution {
public int MatrixScore(int[][] grid) {
int m = grid.Length, n = grid[0].Length;
int score = (1 << (n - 1)) * m;
for (int j = 1; j < n; ++j) {
int colCount = 0;
for (int i = 0; i < m; ++i) {
if (grid[i][j] == grid[i][0]) colCount++;
}
colCount = Math.Max(colCount, m - colCount);
score += colCount * (1 << (n - j - 1));
}
return score;
}
}Using the same concept in C#, it initializes with an optimized assumption and continuously aligns entries to facilitate 1 markings through columns.