LampsGrid | Topcoder Archive

Problem Statement

Jack has bought a rectangular table containing a grid of lamps. Each lamp is initially either "on" or "off". There is a switch underneath each column, and when the switch is flipped, all the lamps in that column reverse their states ("on" lamps become "off" and vice versa).

A row in the grid is considered lit if all the lamps in that row are "on". Jack must make exactly K flips. The K flips do not necessarily have to be performed on K distinct switches. His goal is to have as many lit rows as possible after making those flips.

You are given a String[] initial, where the j-th character of the i-th element is '1' (one) if the lamp in row i, column j is initially "on", and '0' (zero) otherwise. Return the maximal number of rows that can be lit after performing exactly K flips.

Definition

Class:: LampsGrid
Method:: mostLit
Parameters:: String[], int
Returns:: int
Method signature:: int mostLit(String[] initial, int K)
(be sure your method is public)

Constraints

initial will contain between 1 and 50 elements, inclusive.
Each element of initial will contain between 1 and 50 characters, inclusive.
Each element of initial will contain the same number of characters.
Each element of initial will contain only the digits '0' and '1'.
K will be between 0 and 1000, inclusive.

Examples

```
{"01",
 "10",
 "10"}
```
```
1
```
```
Returns: 2
```
Here, Jack must flip exactly one switch. If he flips the switch for the second column, the bottom two rows become lit.
```
{"101010"}
```
```
2
```
```
Returns: 0
```
```
{"00", "11"}
```
```
999
```
```
Returns: 0
```
No row can be lit after exactly 999 flips.

{"0", "1", "0", "1", "0"}

Returns: 2

{"001", "101", "001", "000", "111", "001", "101", "111", "110", "000", "111", "010", "110", "001"}

Returns: 4

{"01", "10", "01", "01", "10"}

Returns: 3

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.