861. Score After Flipping Matrix

Problem

Score After Flipping Matrix

Description

According to the result that is to calculate the sum of these numbers from these binary number, so there is one obvious strategy. For every row, we can flip it if the first element is 0. Because after that, the result will be bigger definitely. And then for every column, every element is in the same postion in their own binary array and if the number of 0 is more than 1’s, so flip it and we can get better result.

Code

class Solution {
    private void flipRow(int[][] A, int row){
        for(int i = 0; i < A[row].length; i ++){
            A[row][i] ++;
            A[row][i] %= 2;
        }
    }
    private void flipCol(int[][] A, int col){
        for(int i = 0; i < A.length; i ++){
            A[i][col] ++;
            A[i][col] %= 2;
        }
    }
    public int matrixScore(int[][] A) {
        if(A.length == 0) return 0;
        int rows = A.length, cols = A[0].length;
        // flip rows whose first element is 0
        for(int i = 0; i < rows; i ++){
            if(A[i][0] == 0) flipRow(A, i);
        }
        // counts1 will record the number of 1 in every column
        int[] count1 = new int[cols];
        for(int i = 0; i < rows; i ++){
            for(int j = 0; j < cols; j ++){
                if(A[i][j] == 1) count1[j] ++;
            }
        }
        // flip columns that contains more element 0 than 1.
        for(int i = 1; i < cols; i ++){
            if(count1[i] < (rows + 1) / 2){
                flipCol(A, i);
            }
        }
        int ans = 0;
        for(int i = 0; i < rows; i ++){
            int cur = 0;
            for(int j = 0; j < cols; j ++){
                cur = cur * 2 + A[i][j];
            }
            ans += cur;
        }
        return ans;
    }
}