QN03  Fan Switches
Problem Statement
It's holiday time at DAIICT, and all the students are back home, enjoying themselves. The professors too are offcampus, 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 n1 ), 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 i^{th} switch ), and then toggle all the switches from the i^{th} one to the n1^{th} one ( both inclusive ). This means that for any given switch in the range [ i, n1 ], 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 i^{th} one ), and then toggling all the switches in the range [ i, n1 ]
Input
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 i^{th} character of this string may either be a '0' or a '1'. A '0' at this position indicates that the i^{th} switch is off, otherwise a '1' at this position indicates that the i^{th} switch is on, in the final configuration.
Output
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.
Example
Input :
4
0011
000
0100
111000111
Output :
1
0
2
3
Explanation:
 In the first test case, all you require is one move wherein you select the 2^{nd }switch, and thus toggle the 2^{nd} and 3^{rd} switches, turning them both on.
 In the second test case, no operations are needed ( since all the fans are switched off in the final configuration anyway )
 In the third test case, a possible sequence of switches selected is  the 1^{st}, and then the 2^{nd}. 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:
20150707 21:59:17
Laziness gave me 3 WA and 1 CE. _ 

Francky:
20130417 19:50:31
Moved to tutorial. 

yaswanth:
20130417 16:57:45
tutorial defintitely!! 

Francky:
20130329 12:48:41
Is there any reason not to move this one to tutorial ? (prior to the elder) 

kamalesh:
20130329 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:
20130304 22:17:51
I think the constraints on this problem should be larger, 1 <= length of the string <= 100,000 at least. Last edit: 20130304 22:18:12 

Yo Yo Honey Singh:
20130224 20:09:56
same as... http://www.spoj.com/problems/PEBBLE/ 
Added by:  Gowri Sundaram 
Date:  20121115 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 