Solution
Approach 1: Brute Force
Intuition
Notice that a 1
in the th column from the right, contributes to the score.
Say we are finished toggling the rows in some configuration. Then for each column, (to maximize the score), we'll toggle the column if it would increase the number of 1
s.
We can brute force over every possible way to toggle rows.
Algorithm
Say the matrix has R
rows and C
columns.
For each state
, the transition trans = state ^ (state1)
represents the rows that must be toggled to get into the state of toggled rows represented by (the bits of) state
.
We'll toggle them, and also maintain the correct column sums of the matrix on the side.
Afterwards, we'll calculate the score. If for example the last column has a column sum of 3
, then the score is max(3, R3)
, where R3
represents the score we get from toggling the last column.
In general, the score is increased by max(col_sum, R  col_sum) * (1 << (C1c))
, where the factor (1 << (C1c))
is the power of 2
that each 1
contributes.
Note that this approach may not run in the time allotted.
Complexity Analysis

Time Complexity: , where is the number of rows and columns in the matrix.

Space Complexity: in additional space complexity.
Approach 2: Greedy
Intuition
Notice that a 1
in the th column from the right, contributes to the score.
Since , maximizing the leftmost digit is more important than any other digit. Thus, the rows should be toggled such that the leftmost column is either all 0
or all 1
(so that after toggling the leftmost column [if necessary], the left column is all 1
.)
Algorithm
If we toggle rows by the first column (A[r][c] ^= A[r][0]
), then the first column will be all 0
.
Afterwards, the base score is max(col, R  col)
where col
is the column sum; and (1 << (C1c))
is the power of 2 that each 1
in that column contributes to the score.
Complexity Analysis

Time Complexity: , is the number of rows and columns in the matrix.

Space Complexity: in additional space complexity.
Analysis written by: @awice.