Best Binary Rows After Flips

Medium

You get a table bits of zeros and ones with m rows and n columns. In one move you may pick any row or any column and flip every bit in it: zeros turn into ones and ones into zeros. Each row is read left to right as a binary number. The value of the table is the sum of these numbers over all rows. Make as many moves as you like (possibly none) and return the largest value the table can reach.

Example 1

bits=[[0, 1, 1], [1, 1, 0]] → 12

Flip the first row to get 100, then the second column: the rows become 110 and 100. That is 6 + 4 = 10, and nothing beats it.

Example 2

bits=[[0, 0], [0, 0]] → 6

Flip both rows: 11 + 11 = 3 + 3 = 6.

Constraints

1 ≤ m, n ≤ 20
All rows have the same length n
bits[i][j] is 0 or 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Bit Manipulation Array Matrix

Similar problems

Raise Towers, Keep the Skyline Medium Two Rows of Lamps Medium Groups of Four at the Cinema Medium Rows Under the Diagonal Medium Bump One or Double All Medium

Input

bits=[[0, 1, 1], [1, 1, 0]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 82 tests on the server, hidden ones included.