[LeetCode] 861. Score After Flipping Matrix

 Problem: https://leetcode.com/problems/score-after-flipping-matrix/

- To get the maximum possible number, we need to flip all grid[y][0] to '1'.

- Because we did flip to the first column on the first step, the value on the grid[y][x] = 1 if grid[y][x] == grid[y][0]. Flip the values on each column to get as much ones as possible.

Because every row represents a binary number,  grid[y][x] is worth 1 << (COLUMN - x -1) points.

class Solution {
    public int matrixScore(int[][] grid) {
        int ROW = grid.length;
        int COLUMN = grid[0].length;
        
        // To get the maximum value, we need to toggle all grid[i][0] to '1'
        // And every grid[i][0] worths 1 << (COLUMN - 1) points
        
        int result = (1 << (COLUMN - 1)) * ROW;
        
        for (int x = 1; x < COLUMN; x++) {
            
            // count of one on current column
            int countOfOne = 0;
            
            for (int y = 0; y < ROW; y++) {
                
                // because we flipped grid[y][0] to 1
                // grid[y][x] will be '1' if it equals to grid[y][0]
                if (grid[y][x] == grid[y][0]) {
                    countOfOne += 1;
                }
            }
                
            int countOfZero = ROW - countOfOne;

            if (countOfZero > countOfOne) {
                // this column has more zeros than ones
                // flip zero to one to get more ones
                countOfOne = countOfZero;
            }

            // every one on this column worths 1 << (COLUMN - x - 1) points
            result += (1 << (COLUMN - x - 1)) * countOfOne;
        }
        
        return result;
        
    }
}