We have a two dimensional matrix A where each value is 0 or 1.
A move consists of choosing any row or column, and toggling each value in that row or column: changing all 0s to 1s, and all 1s to 0s.
After making any number of moves, every row of this matrix is interpreted as a binary number, and the score of the matrix is the sum of these numbers.
Return the highest possible score.
 



Example 1:
Input: [[0,0,1,1],[1,0,1,0],[1,1,0,0]]
Output: 39
Explanation:
Toggled to [[1,1,1,1],[1,0,0,1],[1,1,1,1]].
0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39
 
Note:

1 <= A.length <= 20
1 <= A[0].length <= 20
A[i][j] is 0 or 1.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Matrices

Bit manipulation

Data structures

Greedy algorithms

Starter code: class Solution:
    def matrixScore(self, A: List[List[int]]) -> int:
        

Solutions:
class Solution:

	def matrixScore(self, A: List[List[int]]) -> int:

		def bitFlip(row):
			for (i, r) in enumerate(row):
				row[i] = 1 - r
			return row
		for (i, row) in enumerate(A):
			if row[0] == 0:
				A[i] = bitFlip(row)
		for j in range(1, len(A[0])):
			count = 0
			for i in range(0, len(A)):
				count += A[i][j]
			if count <= len(A) // 2:
				for i in range(0, len(A)):
					A[i][j] = 1 - A[i][j]

		def score(row):
			return sum([r * 2 ** i for (i, r) in enumerate(reversed(row))])
		return sum([score(row) for row in A])


class Solution:

	def matrixScore(self, A):
		(M, N) = (len(A), len(A[0]))
		res = (1 << N - 1) * M
		for j in range(1, N):
			cur = sum((A[i][j] == A[i][0] for i in range(M)))
			res += max(cur, M - cur) * (1 << N - 1 - j)
		return res


class Solution:

	def matrixScore(self, A: List[List[int]]) -> int:
		maxsum = 0
		power = len(A[0])
		for row in A:
			for i in range(power):
				maxsum += 2 ** (power - 1 - i) * row[i]
		while True:
			change = False
			crow = False
			num = 0
			cursum = maxsum
			localsum = maxsum
			for row in range(len(A)):
				for i in range(power):
					term = 2 ** (power - 1 - i)
					if A[row][i] == 1:
						cursum -= term
					else:
						cursum += term
				if cursum > maxsum:
					change = True
					maxsum = cursum
					crow = True
					num = row
				cursum = localsum
			for col in range(power):
				term = 2 ** (power - 1 - col)
				for row in range(len(A)):
					if A[row][col] == 1:
						cursum -= term
					else:
						cursum += term
				if cursum > maxsum:
					change = True
					maxsum = cursum
					crow = False
					num = col
				cursum = localsum
			if change:
				if crow:
					for i in range(power):
						A[num][i] = A[num][i] + (1 - 2 * A[num][i])
				else:
					for row in range(len(A)):
						A[row][num] = A[row][num] + (1 - 2 * A[row][num])
			if not change:
				return maxsum


class Solution:

	def matrixScore(self, A: List[List[int]]) -> int:
		(M, N) = (len(A), len(A[0]))
		ans = (1 << N - 1) * M
		for j in range(1, N):
			count = sum((A[i][j] == A[i][0] for i in range(M)))
			ans += max(count, M - count) << N - j - 1
		return ans


class Solution:

	def matrixScore(self, A: List[List[int]]) -> int:

		def toggle_row(row):
			for j in range(len(A[0])):
				if A[row][j] == 1:
					A[row][j] = 0
				else:
					A[row][j] = 1

		def toggle_col(col):
			for i in range(len(A)):
				if A[i][col] == 1:
					A[i][col] = 0
				else:
					A[i][col] = 1
		for i in range(len(A)):
			if A[i][0] == 0:
				toggle_row(i)
		for j in range(1, len(A[0])):
			col_sum = 0
			for i in range(len(A)):
				col_sum += A[i][j]
			if col_sum < len(A) / 2:
				toggle_col(j)
		res = 0
		for row in A:
			row_s = ''
			for i in row:
				row_s += str(i)
			decimal = int(row_s, 2)
			res += decimal
		return res


class Solution:

	def matrixScore(self, A: List[List[int]]) -> int:
		(m, n, ans) = (len(A), len(A[0]), 0)
		for c in range(n):
			col = sum((A[r][c] == A[r][0] for r in range(m)))
			ans += max(col, m - col) * 2 ** (n - 1 - c)
		return ans


class Solution:

	def matrixScore(self, A: List[List[int]]) -> int:
		total = 0
		for i in range(len(A)):
			if A[i][0] == 0:
				for j in range(len(A[0])):
					A[i][j] = 1 - A[i][j]
		for i in range(len(A[0])):
			colZero = 0
			colOne = 0
			for j in range(len(A)):
				if A[j][i] == 1:
					colOne += 1
				else:
					colZero += 1
			total += max(colOne, colZero) * 2 ** (len(A[0]) - 1 - i)
		return total


class Solution:

	def matrixScore(self, A: List[List[int]]) -> int:
		(N, M) = (len(A), len(A[0]))
		res = 0
		for jj in range(M):
			num = 0
			for ii in range(N):
				num += A[ii][jj] ^ A[ii][0]
			res += max(num, N - num) * 2 ** (M - jj - 1)
		return res


class Solution:

	def matrixScore(self, A: List[List[int]]) -> int:
		(m, n) = (len(A), len(A[0]))
		f = [0] * m
		for i in range(m):
			if A[i][0] == 0:
				f[i] = 1
		ans = 2 ** (n - 1) * m
		for j in range(1, n):
			cnt = sum((f[i] ^ A[i][j] for i in range(m)))
			cnt = max(cnt, m - cnt)
			ans += 2 ** (n - 1 - j) * cnt
		return ans


class Solution:

	def matrixScore(self, A: List[List[int]]) -> int:
		w = len(A[0])
		h = len(A)
		max_row = int(2 ** w) - 1

		def max_col(ci):
			return h * c_val(ci)

		def c_val(ci):
			return 2 ** (w - ci - 1)
		row_sum = [sum((v * c_val(ci) for (ci, v) in enumerate(l))) for l in A]
		col_sum = [sum((A[ri][ci] * c_val(ci) for ri in range(h))) for ci in range(w)]
		flipped = True
		while flipped:
			flipped = False
			for (ri, r) in enumerate(row_sum):
				if r < max_row - r:
					flipped = True
					for ci in range(w):
						A[ri][ci] = 1 - A[ri][ci]
						row_sum[ri] = max_row - r
						if A[ri][ci] == 1:
							col_sum[ci] += c_val(ci)
						else:
							col_sum[ci] -= c_val(ci)
			for (ci, c) in enumerate(col_sum):
				if c < max_col(ci) - c:
					flipped = True
					for ri in range(h):
						A[ri][ci] = 1 - A[ri][ci]
						col_sum[ci] = max_col(ci) - c
						if A[ri][ci] == 1:
							row_sum[ri] += c_val(ci)
						else:
							row_sum[ri] -= c_val(ci)
		return sum(row_sum)


class Solution:

	def matrixScore(self, A: List[List[int]]) -> int:
		(R, C) = (len(A), len(A[0]))
		ans = 0
		for c in range(C):
			col = 0
			for r in range(R):
				col += A[r][c] ^ A[r][0]
			ans += max(col, R - col) * 2 ** (C - 1 - c)
		return ans