861.score-after-flipping-matrix.java

861.score-after-flipping-matrix.java

// https://leetcode.com/problems/score-after-flipping-matrix/description/
// Solution: Greedy.
// It is always good to make first column all 1s, because it is the most significant bit.
// And for other columns, flip if it gives larger result.
// Correctness: We only need to prove it is optimal for 2-columns matrix.
// Though I don't havr formal proof, we can think about any counter cases: 
// is there a case that for a row starting with 0, and we don't flip the row?
// O(R*C) time.
import java.util.*;
class Solution {
    public static void main(String[] args) {
      Solution s = new Solution();
      int[][] A = {{0,0,1,1}, {1,0,1,0}, {1,1,0,0}};
      int rst = s.matrixScore(A);
      System.out.println(rst);
    }
    public int matrixScore(int[][] A) {
      int r = A.length;
      int c = A[0].length;
      for (int i = 0; i < r; ++i) {
        if (A[i][0] == 0) {
          for (int j = 0; j < c; ++j) {
            A[i][j] = 1 - A[i][j];
          }
        }
      }
      for (int i = 0; i < c; ++i) {
        int zc = 0;
        for (int j = 0; j < r; ++j) {
          if (A[j][i] == 0) {
            zc++;
          }
        }
        if (2 * zc > r) {
          for (int j = 0; j < r; ++j) {
            A[j][i] = 1 - A[j][i];
          }
        }
      }
      int rst = 0;
      for (int i = 0; i < r; ++i) {
        int b = 0;
        for (int j = 0; j < c; ++j) {
          b = 2 * b + A[i][j];
        }
        rst += b;
      }
      return rst;
    }
}