Show problems as
Classic problem #861MediumArrayGreedyBit ManipulationMatrix

Score After Flipping Matrix

Real-world version: Maximum Relay Cabinet Total
Tracked in this browser only
Read Score After Flipping Matrix on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A control cabinet holds a stack of relay racks. Every rack carries the same run of relays side by side, and each relay is either closed, written 1, or open, written 0. racks[i][j] is the state of the relay at position j on rack i.

Each rack reports a reading: read its relays from left to right as the digits of a binary number, so the leftmost relay is the most significant digit. The cabinet total is the sum of all the rack readings.

A maintenance panel offers two kinds of switch, and you may throw as many of them as you like, in any order, including none at all:

  • a rack switch picks one rack and flips every relay on it, each closed relay becoming open and each open relay becoming closed;
  • a column switch picks one position and flips the relay at that position on every rack at once.

Return the largest cabinet total you can reach.

Examples

Example 1

Input
racks = [[0, 1, 1, 0], [1, 0, 0, 1], [1, 1, 1, 0]]
Output
38

Throw the rack switch on rack 0, then the column switches at positions 1 and 2. The racks then read 1111, 1111 and 1000, which are 15, 15 and 8, for a cabinet total of 38.

Example 2

Input
racks = [[1, 0, 1], [1, 1, 0]]
Output
11

Left alone the two racks read 101 and 110, which are 5 and 6, for a total of 11.

Example 3

Input
racks = [[1, 0, 0, 1, 0]]
Output
31

With a single rack in the cabinet, throwing the column switches at positions 1, 2 and 4 leaves it reading 11111, which is 31.

Constraints

  • 1 <= racks.length <= 20
  • 1 <= racks[i].length <= 20
  • 0 <= racks[i][j] <= 1
  • Every rack carries the same number of relays.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def best_cabinet_total(racks: list[list[int]]) -> int:
Java
public int bestCabinetTotal(int[][] racks)

More on the same topics