TheDevice | Topcoder Archive

Problem Statement

Manao works at a laboratory on a highly classified project. From time to time, he is given a special device and has to determine its exact structure. Every such device operates on special plates. There are M bits written on each of the plates from left to right. The device has two inputs and a screen. Each input requires a plate. When two plates are connected to the device, M bits of output appear on the screen. Each bit of output is either a binary OR, AND or XOR of the corresponding bits of the input plates. Manao's task is to determine what operation is carried out for each of the bits.

Manao has N plates. He is going to test the device on each possible pair of these plates and determine its structure by the outputs on the screen. It might be that the plates Manao has are not enough to uniquely identify every possible device. You are given String[] plates, where each element describes a plate Manao has. Return the minimum number of additional plates Manao needs to be able to determine the structure of any device.

Definition

Class:: TheDevice
Method:: minimumAdditional
Parameters:: String[]
Returns:: int
Method signature:: int minimumAdditional(String[] plates)
(be sure your method is public)

Constraints

plates will contain between 1 and 50 elements, inclusive.
Each element of plates will be between 1 and 50 characters long, inclusive.
All elements of plates will be of equal length.
Each element of plates will contain characters from the set {'0', '1'} only.

Examples

```
{"010",
 "011",
 "101"}
```
```
Returns: 1
```
It is possible to find two different devices such that no pair of Manao's plates will distinguish between them. To fix this it is sufficient to add one more plate. An example of such a plate is "101". There are also other plates that would work in its place.
```
{"0",
 "1",
 "0",
 "1"}
```
```
Returns: 0
```
With these plates, Manao can test the output for every possible pair of bits, which allows him to distinguish between AND, OR and XOR.
```
{"01010101",
 "10101010"}
```
```
Returns: 1
```

{"10010101011",
 "00010101001",
 "00100010111",
 "00101010101",
 "01010111101"}

Returns: 1

{"1101001011010",
 "0010000010101",
 "1010101011110",
 "1101010100111",
 "1011111110111"}

Returns: 0

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.