Given a string containing the only symbols ‘+’ or ‘-‘, how do we find the minimum number of changes to transform it to a chain. A chain of length N is the sequence of alternative + and – symbols.
For example “+-+-+” is a chain of length 5.
Similarly “-+-+-+” is a chain of length 6.
This is a problem from recently concluded Codechef contest. Here is the link to the original problem.
Some examples of input and output are as follows
Input Output
————–
–+ 1
-+- 0
+-+–+ 2
We can solve this problem as follows.
Observation:
Given the length of the sequence N, there are only two possible chains; One starting with – (-+-+….), and the other starting with + (+-+….).
So it is just enough to compare the input string to these two patterns and find the number of changes to make it a chain. Minimum of these two numbers gives us the answer.
For an example consider the input
+–++
Difference with +-+-+ is 2
Difference with -+-+- is 3
So the minimum number of changes to make it a chain is 2.
Here is the C++ code which implements the above.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| #include <string> | |
| using namespace std; | |
| int main() | |
| { | |
| cin.sync_with_stdio(false); | |
| int t; | |
| cin >> t; | |
| while(t--) | |
| { | |
| string input; | |
| cin >> input; | |
| int i, result = 0, result1 = 0; | |
| char p1 = '+', p2 = '-'; | |
| for( i = 0; i < input.size(); i++ ) | |
| { | |
| if( input[i] != p1 ) | |
| result++; | |
| if( input[i] != p2 ) | |
| result1++; | |
| p1 = (p1 == '+')? '-':'+'; | |
| p2 = (p2 == '+')? '-':'+'; | |
| } | |
| cout << min(result,result1) << endl; | |
| } | |
| return 0; | |
| } |
by