aboutsummaryrefslogtreecommitdiff
path: root/min_num_flip_bin_grid_palin2.c
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-04-15 20:04:10 -0600
committerJack Sangdahl <[email protected]>2025-04-15 20:04:10 -0600
commit87c40729389ab33c8ad1a86faf6f45e9d8b20fe4 (patch)
tree4209d18287daec663de3b01bfcf95ac76b1e0fd4 /min_num_flip_bin_grid_palin2.c
parente7bc454ca4a66df33ad0db3c69ff3f68b529f008 (diff)
downloadleetcode-87c40729389ab33c8ad1a86faf6f45e9d8b20fe4.tar.gz
leetcode-87c40729389ab33c8ad1a86faf6f45e9d8b20fe4.zip
3240. minimum number of flips to make binary grid palindromic 2
Diffstat (limited to 'min_num_flip_bin_grid_palin2.c')
-rw-r--r--min_num_flip_bin_grid_palin2.c50
1 files changed, 50 insertions, 0 deletions
diff --git a/min_num_flip_bin_grid_palin2.c b/min_num_flip_bin_grid_palin2.c
new file mode 100644
index 0000000..fe3ffdf
--- /dev/null
+++ b/min_num_flip_bin_grid_palin2.c
@@ -0,0 +1,50 @@
+// 3240. Minimum Number of Flips to Make Binary Grid Palindromic II
+#include "leetcode.h"
+
+/*
+ * you are given an 'm x n' binary matrix 'grid'. a row or column is considered
+ * palindromic if its values read the same forward as backward. you can flip any
+ * number of cells in 'grid' from 0 to 1 or from 1 to 0. return the minimum
+ * number of cells that need to be flipped to make all rows and columns
+ * palindromic and the total number of 1s in 'grid' divisible by 4.
+ */
+
+int minFlips(int **grid, int gridSize, int *gridColSize) {
+ int ans = 0, one = 0, diff = 0, m = gridSize, n = gridColSize[0];
+ for (int i = 0; i < m / 2; ++i)
+ for (int j = 0; j < n / 2; ++j) {
+ int v = grid[i][j] + grid[i][n - 1 - j] + grid[m - 1 - i][j] +
+ grid[m - 1 - i][n - 1 - j];
+ ans += fmin(v, 4 - v);
+ }
+ if (n % 2)
+ for (int i = 0; i < m / 2; ++i) {
+ diff += grid[i][n / 2] != grid[m - 1 - i][n / 2];
+ one += grid[i][n / 2] + grid[m - 1 - i][n / 2];
+ }
+ if (m % 2)
+ for (int j = 0; j < n / 2; ++j) {
+ diff += grid[m / 2][j] != grid[m / 2][n - 1 - j];
+ one += grid[m / 2][j] + grid[m / 2][n - 1 - j];
+ }
+ if (n % 2 && m % 2)
+ ans += grid[m / 2][n / 2];
+ if (!diff && one % 4)
+ ans += 2;
+ return ans + diff;
+}
+
+int main() {
+ int g1i[3][3] = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}},
+ g2i[3][2] = {{0, 1}, {0, 1}, {0, 0}}, g3i[2][1] = {{1}, {1}};
+ struct two_d_arr g1, g2, g3;
+ two_d_arr_init(&g1, ARRAY_SIZE(g1i), ARRAY_SIZE(g1i[0]), g1i);
+ two_d_arr_init(&g2, ARRAY_SIZE(g2i), ARRAY_SIZE(g2i[0]), g2i);
+ two_d_arr_init(&g3, ARRAY_SIZE(g3i), ARRAY_SIZE(g3i[0]), g3i);
+ printf("%d\n", minFlips(g1.arr, g1.row_size, g1.col_size)); // expect: 3
+ printf("%d\n", minFlips(g2.arr, g2.row_size, g2.col_size)); // expect: 2
+ printf("%d\n", minFlips(g3.arr, g3.row_size, g3.col_size)); // expect: 2
+ two_d_arr_free(&g1);
+ two_d_arr_free(&g2);
+ two_d_arr_free(&g3);
+}