Score After Flipping Matrix

Check out the problem statement on this link.

Score After Flipping Matrix - LeetCode

Approach 1:

This problem can be solved by greedy approach and bit manipulation.

a)For Rows

where we first traverse over the rows first and then we check if flipping 0’s to 1's and 1’s to 0’s can give a binary number for that row, that is greater than current binary number for that row. If yes then we flip the bits for that row. And this is done for all the rows.

b)For Columns

Now we iterate across the column. Now we traverse the column. And for columns to get maximum final sum , we should flip the bits for a column if number of 0’s on that column is greater than the number of 1' s, as a result of which we greater number of 1’s for that column , yielding greater sum.

class Solution:
    def matrixScore(self, grid: List[List[int]]) -> int:
        col_size=len(grid[0])
        row_size=len(grid)
        mask=(1<<col_size)-1
        for i in range(row_size):
            val=0
            for j in grid[i]:
                val<<=1
                val|=j
            if(val^mask>val):
                val1=val^mask
                cnt=1
                while(val1):
                    bit = val1&1
                    grid[i][col_size-cnt]=bit
                    cnt+=1
                    val1>>=1        
        for j in range(col_size):
            count_zero=0
            count_one=0
            for k in range(row_size):
                if(grid[k][j]==0):
                    count_zero+=1
                else:
                    count_one+=1
            if(count_zero>count_one):
                print(count_zero,"j",j)
                for i in range(row_size):
                    if (grid[i][j]==0):
                        grid[i][j]=1  
                    else:
                        grid[i][j]=0
        sum_=0
        for i in grid:
            cnt=1
            for j in i:
                sum_+=(2**(col_size-cnt))*j
                cnt+=1
        return sum_            

Time : O(rows*columns)

Space: O(1)