LightSwitchingPuzzle | Topcoder Archive

Problem Statement

Leo has N lights in a row. The lights are numbered 1 through N. Each light is either on or off.

Leo wants to turn all the lights off. He has N switches he may use. The switches are also numbered 1 through N. For each i, switch number i toggles the state of all lights whose numbers are multiples of i. (For example, switch 3 will toggle the state of light 3, light 6, light 9, and so on.)

You are given the current state of all lights as a String state with N characters. For each valid i, state[i] is either 'Y' (meaning that light i+1 is currently on) or 'N' (meaning that the light is off). Determine the smallest number of switches Leo needs to press in order to turn off all the lights. If there is no way to turn off all the lights, return -1 instead.

Definition

Class:: LightSwitchingPuzzle
Method:: minFlips
Parameters:: String
Returns:: int
Method signature:: int minFlips(String state)
(be sure your method is public)

Constraints

state will contain between 1 and 1000 characters, inclusive.
Each character of state will be either 'Y' or 'N'.

Examples

```
"YYYYYY"
```
```
Returns: 1
```
We can turn off all the lights by pressing switch 1.
```
"YNYNYNYNY"
```
```
Returns: 2
```
We cannot turn these lights off in a single step. It can be done in two steps. One possible solution looks as follows: First, press the second switch. This will toggle lights with numbers 2, 4, 6, and 8. The state of the lights after this change will be "YYYYYYYYY". Next, press the first switch to toggle all lightbulbs.
```
"NNNNNNNNNN"
```
```
Returns: 0
```
All the lights are already off.
```
"YYYNYYYNYYYNYYNYYYYN"
```
```
Returns: 4
```

"NYNNYNNNYNNNNYNNNNNYNNNNNNYNNNNNNNY"

Returns: 12

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.