Thursday, February 19, 2015

Minimum number of symbols to change to make a chain

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.