Logical | Topcoder Archive

Problem Statement

Any logical statement can be written in the following format:

(<Var> or <Var>) and (<Var> or <Var>) and ... and (<Var> or <Var>)

<Var> can be a capital letter, or '~'(not) followed by a capital letter. Each "(<Var> or <Var>)" is called a BLOCK. For example:

"(P or P) and (~R or P) and (Q or Q)" is a logical statement with 3 BLOCKs.

A logical statement can be MADE TRUE if there is a way of assigning truth values to the capital letters used, such that the entire statement evaluates to true. The previous example can be MADE TRUE since setting P and Q to true, and R to either true or false will make the statement true. Given a logical statement as a String[] of blocks, you will determine the minimum number of blocks that have to be removed such that the statement can be MADE TRUE. For example:

statement = {"P or Q","~P or ~P"}
This corresponds to the statement "(P or Q) and (~P or ~P)".  
This statement can already be MADE TRUE so your method would return 0.
statement = {"P or P","~P or ~P"}
This corresponds to the statement "(P or P) and (~P or ~P)".  
Removing either block will enable this statement to be MADE TRUE.  
Your method would return 1.

Create a class Logical that contains the method howMany, which takes a String[] statement, and returns an int that represents the minimum number of blocks that need to be removed such that the statement can be MADE TRUE.

Definition

Class:: Logical
Method:: howMany
Parameters:: String[]
Returns:: int
Method signature:: int howMany(String[] statement)
(be sure your method is public)

Constraints

statment must contain between 1 and 10 elements inclusive
Each element of statement must be of the form(quotes for clarity): " or " where can be either a capital letter ('A'-'Z'), or '~' followed by a capital letter

Examples

```
{"P or P","~R or P","Q or Q"}
```
```
Returns: 0
```
This was one of the examples stated in the problem. The statement can already be MADE TRUE by making P, and Q true and R either false or true.
```
{"P or Q","~P or ~P"}
```
```
Returns: 0
```
This example was also mentioned in the problem statement. Making P false and Q true will make this statement true thus the statement can be MADE TRUE as is.
```
{"P or P","~P or ~P"}
```
```
Returns: 1
```
As mentioned in the problem, this statement cannot be MADE TRUE. If we remove either block the statement can be MADE TRUE.

{"P or P","Q or Q","P or P","Q or Q","~P or ~Q","~P or ~Q"}

Returns: 2

This example shows that statements can be duplicated.

```
{"P or Q"}
```
```
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.