Question
Contiguous Ones Challenge
In the magical realm of CodeLand, your wise teacher has presented you with a captivating challenge to test your programming skills. You have been given a binary string X, a special sequence made up of only ‘0’s and ‘1’s.
Your mission is to gather all the ‘1’s together, forming a perfect block of happiness without any ‘0’s interrupting their unity. To achieve this, you possess a powerful ability: you can pick any index i (where 0 < i < n - 1, and n is the length of the string) and reverse the portion of the string from the start to that index.
Now, the quest is clear: determine the minimum number of moves required to bring all the ‘1’s together in a contiguous block. Are you ready to embark on this coding adventure and prove your prowess?
Input
The line of the input contains a single integer N.
The second line of the input contains a string of length N.
Constraints
1 ≤ N ≤ 105
String contains only the characters '0' and '1'.
The second line of the input contains a string of length N.
Constraints
1 ≤ N ≤ 105
String contains only the characters '0' and '1'.
Output
Print the minimum number of moves you will have to make to accomplish the given task.
Example
Sample Input
9
00110111
Sample Output
2
Explanation
Currently our string s is "00110111".
In the first move, we can reverse the prefix of length 4 i. e. "0011". Now s = "11000111"
Then we can reverse the prefix of length 5 i. e. "11000". Now s = "00011111"
As we can see all the '1' are consecutive now. Also there is no way possible to achieve the same in less than 2 moves.
9
00110111
Sample Output
2
Explanation
Currently our string s is "00110111".
In the first move, we can reverse the prefix of length 4 i. e. "0011". Now s = "11000111"
Then we can reverse the prefix of length 5 i. e. "11000". Now s = "00011111"
As we can see all the '1' are consecutive now. Also there is no way possible to achieve the same in less than 2 moves.