QN03 - Fan Switches

no tags 

Problem Statement

It's holiday time at DA-IICT, and all the students are back home, enjoying themselves. The professors too are off-campus, since they have no work to do and are finally free. Seems like the whole campus is empty, and everyone's having a lot of fun, but this is not true - the RC is still open, and Rahu, the bored librarian, still has to sit at his desk and work, even though there are no books to issue, and no late fines to collect.

It's 9:30 AM and Rahu has just unlocked the doors of the RC. He sees n fan switches on the wall ( numbered 0 to n-1 ), all initially off. Since no one's in the RC at the moment, he knows that he only needs to switch on a subset of these switches, and since he has nothing to do and a lot of time to kill, he decides to turn this into a game. He decides to select a particular switch ( say the ith switch ), and then toggle all the switches from the ith one to the n-1th one ( both inclusive ). This means that for any given switch in the range [ i, n-1 ], if it was initially on, it will now be off, and vice versa. He does so repeatedly until only the appropriate fans are on, and all the rest are off.

You are given the final configuration of the switches required. Assuming that all the fans are initially off, please print out the minimum moves required by Rahu to reach this final configuration.

Note : Here, one move is defined as selecting a particular switch ( say the ith one ), and then toggling all the switches in the range [ i, n-1 ]



The first line contains a single integer T ( T <= 100 ), denoting the number of test cases. T lines of test cases follow.

Each test case consists of a single line containing the binary string finalConfig, the final configuration of the switches required. The length of this string  does not exceed 1000 characters.

The ith character of this string may either be a '0' or a '1'. A '0' at this position indicates that the ith switch is off, otherwise a '1' at this position indicates that the ith switch is on, in the final configuration.



For each test case, output a single line containing the minimum number of moves required to reach this final configuration, from the initial configuration wherein all the fan switches are off. Please note the definition of a "move" at the end of the problem statement.



Input :


Output :


  1. In the first test case, all you require is one move wherein you select the 2nd switch, and thus toggle the 2nd and 3rd switches, turning them both on.
  2. In the second test case, no operations are needed ( since all the fans are switched off in the final configuration anyway )
  3. In the third test case, a possible sequence of switches selected is - the 1st, and then the 2nd. The sequence of all intermediate configurations achieved is as follows : 0000 ( initially ) -> 0111 ( after selecting switch #1 ) -> 0100 ( after selecting switch #2 )


hide comments
Dushyant Singh: 2015-07-07 21:59:17

Laziness gave me 3 WA and 1 CE. -_-

Francky: 2013-04-17 19:50:31

Moved to tutorial.

yaswanth: 2013-04-17 16:57:45

tutorial defintitely!!

Francky: 2013-03-29 12:48:41

Is there any reason not to move this one to tutorial ? (prior to the elder)

kamalesh: 2013-03-29 12:17:33

i just copied and pasted the solution of this problem http://www.spoj.com/problems/PEBBLE/ and AC!!!!! ha ha

david_8k: 2013-03-04 22:17:51

I think the constraints on this problem should be larger, 1 <= length of the string <= 100,000 at least.

Last edit: 2013-03-04 22:18:12
Yo Yo Honey Singh: 2013-02-24 20:09:56

same as... http://www.spoj.com/problems/PEBBLE/

Added by:Gowri Sundaram
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64