LightSwitchingPuzzle

SRM 642 · 2014-08-25 · by lg5293

SRM 642 · 2014-08-25 · by lg5293 · Brute Force, Simple Search, Iteration

Show categories

Class Name: LightSwitchingPuzzle

Return Type: int

Method Name: minFlips

Arg Types: (string)

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.

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

Submissions are judged against all 45 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class LightSwitchingPuzzle with a public method int minFlips(string state) · 45 test cases · 2 s / 256 MB per case