aboutsummaryrefslogtreecommitdiff
path: root/score_after_flipping_matrix.c
diff options
context:
space:
mode:
Diffstat (limited to 'score_after_flipping_matrix.c')
-rw-r--r--score_after_flipping_matrix.c49
1 files changed, 49 insertions, 0 deletions
diff --git a/score_after_flipping_matrix.c b/score_after_flipping_matrix.c
new file mode 100644
index 0000000..bde1b04
--- /dev/null
+++ b/score_after_flipping_matrix.c
@@ -0,0 +1,49 @@
+// 861. Score After Flipping Matrix
+#include "leetcode.h"
+
+/*
+ * given an 'm * n' binary matrix 'grid'. a move consists of choosing any row or
+ * column and toggling each value in thatrow or column. 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.
+ */
+
+int matrixScore(int **grid, int gridSize, int *gridColSize) {
+ int m = gridSize, n = *gridColSize;
+ // flip rows to obtain msb = 1
+ for (int i = 0; i < m; ++i) {
+ if (grid[i][0])
+ continue;
+ for (int j = 0; j < n; ++j)
+ grid[i][j] = !grid[i][j];
+ }
+ // flip columns
+ for (int i = 0; i < n; ++i) {
+ int zeros = 0, ones = 0;
+ for (int j = 0; j < m; ++j) {
+ if (!grid[j][i])
+ ++zeros;
+ else
+ ++ones;
+ }
+ if (ones >= zeros)
+ continue;
+ for (int j = 0; j < m; ++j)
+ grid[j][i] = !grid[j][i];
+ }
+ int ans = 0;
+ // form binary string and convert to integer
+ char *bin_str = (char *)malloc((n + 1) * sizeof(char));
+ for (int i = 0; i < m; i++) {
+ int k = 0;
+ for (int j = 0; j < n; ++j) {
+ bin_str[k] = grid[i][j] + '0';
+ ++k;
+ }
+ k = 0;
+ ans += strtol(bin_str, NULL, 2);
+ }
+ free(bin_str);
+ return ans;
+}