Score After Flipping Matrix Problem

0 like 0 dislike
295 views

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 `0`s to `1`s, and all `1`s to `0`s.

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. `1 <= A.length <= 20`
2. `1 <= A[0].length <= 20`
3. `A[i][j]` is `0` or `1`.

0 like 0 dislike
by Goeduhub's Expert (2.3k points)

Assume A is M * N.

A[i][0] is worth 1 << (N - 1) points, more than the sum of (A[i][1] + .. + A[i][N-1]).

We need to toggle all A[i][0] to 1, here I toggle all lines for A[i][0] = 0.

A[i][j] is worth 1 << (N - 1 - j)

For every col, I count the current number of 1s.

After step 1, A[i][j] becomes 1 if A[i][j] == A[i][0].

if M - cur > cur, we can toggle this column to get more 1s.

max(cur, M - cur) will be the maximum number of 1s that we can get.

Complexity:

Time O(MN)

Space O(1)

class Solution:

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

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

eg : ans = Solution()

ans.matrixScore( [[0,0,1,1],[1,0,1,0],[1,1,0,0]])

Output -

39

Learn & Improve In-Demand Data Skills Online in this Summer With  These High Quality Courses[Recommended by GOEDUHUB]:-

Best Data Science Online Courses[Lists] on:-

Claim your 10 Days FREE Trial for Pluralsight.