One thing note was that trying all combinations was crazy stupid, since it is a runtime of 2^(M*N) so there was a way that we had to optimize
class Solution(object):def matrixScore(self, A):"""https://leetcode.com/problems/score-after-flipping-matrix/description/:type A: List[List[int]]:rtype: int"""R, C = len(A), len(A)ans = 0for c in range(C):col = 0for r in range(R):col += A[r][c] ^ A[r]ans += max(col, R - col) * (1 << (C - 1 - c))return ans
This one took a while. Making the most significant bit one will give the highest return since if those are one then we can get a sum of at least R * 2^(C-1). Once we have decided to toggle all of those to be one, we have to iterate through all of the other columns to decide which ones to toggle based on the number of ones that they have, and toggle only if they have less ones than zeroes
An optimized way to do this would be XOR all the columns with the first column and decide which ones to toggle based on their counts of ones.
Calculating the end sum can be optimized even further by using bit shifting since we have to calculate a power of 2
Time Complexity: O(R*C) where R and C are the dimensions of the matrix
Space Complexity: O(1)